I have done exactly what you want. In fact I've retitled my whole music
database then changed my mind and retitled them again, and again. The
programme I use is Media Center 10 from J River. It's a big programme which
organises all your media (audio, video and pics) into easy to use format by
tagging. Yoy say your files are already tagged so all you need is a
programme that will rename your files according to a new sequence of tags.
OK, Media center will do this for you. Once you have imported all your files
into Media Center and all the tags show correctly, then you select all the
files to be renamed, select Library Tools in right click, then select Rename
Files From Properties. You will be asked what rule you want for folders and
file names - it will offer you suggestions or you can make up your own. And
then hit the buttons and the programme will rename them all. If you change
your mind, which I did (for Winmx purposes), nothing is lost because the
info is all in the tags.
Media Center is downloadable for a 30 day trial, full use from:
http://www.jrmediacenter.com/index.html
and then it is $25. I am on my last day of the trial and I will be paying.
There may be other programs. Media Jukebox is Media Center's predecessor
which is still available, but Media Center is better.
I haven't figured out how to rename through Explorer either.
All the best