I have wrestled trying to get album art on my Kenwood DNX Navi.
1 out of 10 would work right using Media Monkey and Tag & Rename.
I had used Mp3tag in the past so thought I'd give it a try.
Dude...it works perfect...everytime.
I've got the album art on my ATT Fuze phone as well. I can plug the phone into the USB on my DNX and once it loads...album art is there.
Now I just put all my tunes on my ATT Fuze. I have an 8 gig micro SDHC card. This is pure sweetness.
PS...I will give you some cash as soon as I get it.