What about using an uniform 8bpp palette?
http://rlyeh.wordpress.com/tag/uniform-palette/
Hope that helps.
To be honest, im not that experienced with using palettes. Which seems is necessary with 8 bpp.
I would have thought if it was a palette problem the colors only be off, in this case the resolution is also messed up.
I may take a detailed look at what Orkie did with fceu and libcastor.