I have pretty much the exact same problem with a few twists. First, I upgraded to ITunes 9 and then I upgraded to Snow Leopard - all in the same day. Afterward the ITunes screensaver would only display the same three or four albums over and over again. I have over 800+ albums all with art so I knew something was wrong.
My first attempt was to remove the Album Art folder in /music/itunes which simply caused the screen saver to display no album art at all. The folder was recreated, but it was empty at this point. When I resync'd my ipod, a Cache folder was created in the Album Art folder with tons of .itc files. Unfortunately the screensaver still thinks that there is no album art. I tried resetting the screensaver with no luck either.
Here's where it gets a little strange.... first off, all of my artwork is in the mp3 files (I manually added them a while back). However, if I go to "Get Album Artwork" in itunes, the screensaver starts working again but only with the artwork that was downloaded and only displaying the same three or four covers over and over. So there appears to be some issue with the screensaver reading the artwork from the files themselves instead of using what ITunes downloads.
At this point I have given up, but I would like a fix eventually. Anyone out there at Apple watching these threads? Or does anyone know how to alert Apple to this bug? I filed a "feedback" on ITunes but I'm not confident anyone is going to see it.