Leslie,
You're right that looks real bad. OK here are a couple of "dumb" questions. Please remember I'm no expert at LCDs.
Have you done a pin check on your cable and confirmed that every connection has low resistance and that there are no shorts? What I did was do a pin to pin check from connector to connector on my homemade cable, then I did a pin to every other pin check to make sure there were no shorts.
Does your windows screen look ok? Mine does and so does WinAmp.
Have you tried the GPS SW on a regular monitor at 256 to see what it looks like?
have you tried the GPS sw on a Laptop at 256 colors?
Have you tried using 16 bit color? (I'm sure you have but I just have to ask)
Here's why:
256 colors = 256 colors Duh

Alot of stuff looks pretty bad with only 256 colors including winamp.
12 bit = ~4000 colors
16 bit = ~256,000 colors
On the pic I can see red, blue, and green so i have to presume you are getting all the colors. The problem might be you're not getting all the LSBs which is wreaking havoc on your screen pic. maybe at 16 bits you'll get all 4000 colors and it will look better.
Note that the 12 bit screens really don't look that good for DVDs/movie playback but my screen looks good with Windows, Winamp, Sonique, etc. and looks OK for some games (MTM II and kids educational games). I don't have GPS SW so i can't comment on that.
Hope that helps.
Pigseye