The problem (probably) lies in the fact that while the images
look like photographs to us, they are just images with very, very few colors. The use of dithering makes the colors blend more so we perceive them for what they originally were - photographs.
There are many dithering methods and undithering algorithms, but just eyeballing it I think Umihara Kawase uses Floyd-Steinberg. Linux and Mac users can try
undither, a program by kornelski.
(I'm at work right now and stuck in a windows environment but i'll try when i get home unless someone beats me to it)