It's a little late, but none the less this is how I have solved this.
First: I use Ubuntu, so I use easytag... I noticed with easytag that the embedded coverart in my MP3's is labeled with certain descriptions such as (Front Cover) (Back Cover) (Other) etc.... etc.. etc... Whenever the coverart was labeled with anything other than (Front Cover) or (Other), XBMC would not find it. So you must fix all your embedded art in your MP3's first. <---- i know, that sux
Second: In XBMC remove your source<--- go to file mode, go to root, select your music source and remove it completely.
Third: from a terminal, (Not sure how you Windoze folks do it, sorry

) find in the .xbmc/userdata/Thumbnails/Music <--- delete or move that folder
Forth: from a terminal, (Not sure how you Windoze folks do it, sorry

) find in the .xbmc/userdata/Database/MyMusic18.db <--- delete or move that file
Finally: restart XBMC, add your source back, scan your files, update your library and hopefully it will work for you also! Cheers!