As Bill Wittress (Zuneguy) promised, it seems our album art is finally receiving an upgrade. Several Zunerama forum members have noticed that once-pixilated and fuzzy have been replaced with sharp, high-resolution album art scans. Poster MrJoe has also noticed that the "find album info" dialog has been updated and the "find info for all albums" command actually works correctly for once.
One weird thing I noticed about the new dialog is that if I click on the album art during the update, I'm taken to http://shopformusic.microsoft.com/, which seems pretty inconsistent with the Zune branding. I can only hope they fix/update this by the time the new software is released.
The albums appear to be getting their updates artist by artist, likely in time for the launch of Zune2.