This may not be your problem, but it's worth checking. I can't use the Album Art Downloader found at http://louhi.kempele.fi/~skyostil/projects/albumart/ on any MP3 file you've saved Unicode tags in. It complains that the Byte Order Mark isn't found. Now, I know id3v2 makes the BOM optional, but you have to set the frame field that determines with the tag is Unicode or ISO8859-1 to the value that says "I'm using Unicode with no BOM".
Any chance you're setting it to the one that says there's a BOM there, and then not including one? If not, it's the other guy's bug, but I wanted to make sure.