This seems to be hit or miss; my iPod Classic has this problem, but my 3GS did not until I recently updated my album in iTunes.
The album art is embedded in the ID3 tag of the MP3 file for all of my music. The album art displays fine on my computer, and on the iPhone display, but recently, when connected to my AVIC 710, the art is all pixelated, as if it were being blown up, and some album art is even displayed as missing even though I am able to see the jpg exists on the iPod.
Has anyone else seen this?