I realise it seems to be made for Sansa, but the solution worked great for me.
You can re-size the art in an MP3 to a prefered default by using a short command line to change the default (instruction in the Help Files). I just figured that 250x250 was close enough and actually a little smaller than the recommended size, so I used this.
One other small point is that this tool only seems to re-size JPG tags. PNG etc will staill have to be done manually. But as I said, it saved me hours so far.
Let me know if you find a better solution.
You don't HAVE to resize.... and I did say it's not an ideal solution. But it worked for me until/if ever Apple fix the bug. I'm not forcing anyone to take up the solution. Just offereing help if you want it...You could always keep the very slow CoverFlow. I just offered a possible fix based on my findings. I proved IN MY CASE the slow coverflow was definately due to large album art.
I also agree that the resolution will be lower if you go all the way to 250x250 pixels, but on my iPhone 4 AND on my PC, I didn't notice any real degradation. That said, the tool I offered allows you to set the default resolution to anything you like..... The instruction on how to change the default is in the Help files.
For info, I always previously set my album art to a minimum of 600x600 pixels. In some cases my Album Art was larger than 1000x1000 pixels. Personally though, after this, I'm happy to compromise. Like I say. That's my choice...
Finally, if you don't want to reset all your original MP3s artwork. A plan B would be to copy a selection of your music collection to a second location as a trial. That way you will not compromise your original collection. You can always switch the default location for Music in iTunes.... Try with your original artwork verses the reduced size artwork. That's what I did.....
Just a thought.....