I use an app instead of Windows Explorer called: Explorer XP {company link} It offers some robust renaming options. Or you could try to find some freeware renaming app.
I recently used File Renamer, since it was free, and can be founds at download.com.
It was helpful in renaming all the SE5 planet textures and portraits I made.