1. Close Microsoft Media Player for at least 30 seconds
2. Click Start and then Run
3. Type the following into the textbox:
%userprofile%Local SettingsApplication DataMicrosoftMedia Player

4. Click OK and a folder showing you your library files will appear
5. Erase all the files that end with .wmdb
6. Open Microsoft Media Player
7. Push F3
8. Select the locations for your music files
9. WMP will reindex your music

Links

http://www.tech-recipes.com/rx/1045/wmp_how_to_erase_reset_correct_windows_media_library