Someone else had a similar problem in the last 2 or 3 weeks. It turned out that their firewall was blocking MC. You should expect to get at least 90% of the cover art.
Select a few and right click, then Cover Art, Get from Internet.
Name a few popular albums that won't work and maybe someone else can check them.
