Sorry to grave dig but, i am having the same problem with WMP12.0.7601.17514
So for long while my music library has been corrupt, it would play but, would not keep playing ie shuffle, i ran the trouble shooter some time back and it said corupt library.
So what i did was try to weed out the corrupt music, what i found was it was not corrupt music BUT, that it was not the music it is WMP 12 it can not handle any more than 19982 songs or 2193 albums. at first i thought maybe it was the portion of music i was adding and removing finding this bug but, it is not then i thought maybe it is just to much to store in the "current" so i made 4th folder and my music collection is split up in 3 folders. adding the 4th fodler made not difference it can not shuffle or continuous play after19982 songs or 2193. It will play them just fine BUT, no continuous play or shuffle unless in some play list or artist/album sub section.
I am about to confirm this on completely different computer.