It struck me as really odd that this issue still exists after 2+ years, but it does. I got my iphone5 in Novemmeber, choosing it primarily because it has the best camera on the market and I wanted to be able to manage all of my music in iTunes. Managing my music worked great, for about 3 weeks, then I started having the same issue as everyone else here with my album art.
I am an admittedly old school guy when it comes to music, I want to own it. I prefer having it on my device as opposed to streaming it. I am also a Graphic Designer by trade, so the art is something thats pretty important to me. So I set out to find the fix for this, and unfortunately it comes with a cost. The root of the problem, at least for me, is iTunes and how it handles the art. Now, I don't pretend to know exactly what all goes into that, but I do know when I remove all of my music from the phone and add it using another program the art shows up properly. The moment i try to use iTunes to add any music or playlists it starts messing up the art again. Once the art is messed up again, the only way to fix it is to remove the affected files and re-add them, which unfortunately will mess up any playlists you have made on your iPhone.
So this comes down to a choice, you can have your art but you will have to use another program to add/remove your files to the iPhone. Here is how I currently manage my music:
The first thing you have to do is tell your iphone you want to manage your music manually. This is done on the summary screen for the phone, in the options pane at the bottom. The you have to use something else to manage your files, I use a program called MediaMonkey to add/remove the music I want. I am sure there are many options for this. The downside to this method is if you want to use playlists, like I like to do, you will have to manually re-make them all in iTunes AFTER you have added the music you want to the phone. To be sure there are no conflicts I make sure iTunes is closed, open MediaMonkey and add all the music files I want and then close out of it once it is done. I then open iTunes and make my playlists.
Needless to say when you are working with 20+ gigs of files this is a combersome process and may not be for everyone. I hope this helps someone, but in the end I would hope Apple would fix this issue. With apple being such a image driven company, basing so much of their marketing on the "look and feel" of their products, I am kind of surprised this issue has lingered for so long.