Here are the results of pngnq which does exactly the same thing as this tool. It created a file size of 46K, (which I was then able to reduce to 41K with pngout followed by advpng).

http://i.imgur.com/VPc2k.png

http://pngnq.sourceforge.net/

256 colors may simply not be enough for this image.

(Incidentally I was able to slightly reduce your image to 46K with pngout.)