Can't play music files on NAS - help?

I have a Freeagent 300GB external drive hooked up to my WRT350N as a NAS. I backed up my mp3 library here and used to be able to play them from any computer (plays via WMP as a default). A couple of days ago it started to complain with the following message: "Windows Media Player cannot find the file. If you are trying to play, burn, or sync an item that is in your library, the item might point to a file that has been moved, renamed, or deleted." I tried to add the drive to the library, but I still get the same message when I try to play the file.

What's weird though is I previously disconnected and re-mapped this drive many times, and still I could play files. It only seems to happen if I use WMP to play the file, if I open it with Quicktime, the files work.

I also tried to hook up the Freeagent directly to the PC via USB, and I was able to play the files with WMP.

What about opening individual mp3 files with WMP?

Because if you're using WMP's database to play/find your mp3 library, any filepath or drive letter change renders it useless.