Ummm, you might not wanna put too much faith in what I said in my previous post. I thought it was as 'simple' as I made it out to be, and I swear that method used to work in previous versions of iTunes, but there seems to be more to it now. I copied my "iTunes Music" folder to a new location, then specified that location in iTunes preferences, and all was working fine. I even renamed my old iTunes Music folder so that I could be sure iTunes wasn't still using it. Since everything was working ok I deleted the old, renamed iTunes Music folder.
Suddenly iTunes started complaining it couldn't find any of my music. I'm getting the same error the OP is getting. Crap. It's all there, in the new iTunes Music folder, but iTunes can't find it. I tried using "add to library" on a test album, only to find the songs now show up twice in the library, one instance that would play and another that wouldn't.
I should have just deleted everything from the library and just re-added it all, and in fact that's what I'm doing, but I started doing it piecemeal and now I have to finish doing it that way (or risk deleting something that's already been legitimately added, and losing it for good). It's not that big of a deal, I'll get everything added back in, but the bad thing is it'll wipe out all my playlists, playcounts, etc, etc. Oh well, at least the music's not gone...