I also had this issue with much of my album art not showing up on the phone, but ultimately I fixed. I tried just copying my iTunes library files onto my phone (or the SD card), but the only pictures that the phone recognized were ones that I applied manually to the songs, such that any pictures that iTunes found for me did not show up. My solution was a little tedious and probably not ideal for some of you, but I ended up using "Mp3tag" to apply a new picture to each album that did not previously show up. This works whether your music files are on your SD card or directly on your phone. That software is also nice since it lists the song library on your phone if you select it to, and it indicates which music files don't have album art applied to them so that you know which ones to search for.
Anyway, this worked for me and took ~30 minutes to complete the process for my 250-song library. I also had an issue with the phone simply not recognizing some pictures once they were already applied, but just rebooting the phone and the music player a couple of times fixed this.