You're right, these guys just don't know how to create indexed PNGs properly. I ran their originals through Photoshop, with 100% dither at 96 colors, then used pngout (the best* png compressor), and came out with better looking, smaller files.

* http://advsys.net/ken/utils.htm