Album art on my iOS device differs from Mac iTunes
I had the exact same problem several times in the last three years (with an iPhone 3G, an iPhone 4 &amp; an iPod touch).

I always solved it this way :


disable music syncing for the device (uncheck everything in the "music" tab)
sync the device at least two times
enable music syncing
sync again


I usually divide steps 3 &amp; 4 in smaller steps. I begin by syncing a few artists to check everything is fine before syncing all the music I want on my device.

I hope this will work for you.