A program called PowerRen 2000 can do exactly what you want. It's pretty much disappeared from the Web in its free form, but this site has it yet:

PowerRen 2000

You'll want to do the files in batches according to the number of characters preceding the first letter of the desired file name, but it's still a lot faster than one by one.

If you have any trouble downloading it, post back and I'll work out a way to get it to you if you have an email account where you can receive a 1.6mB attachment.

Good luck!