Everybody hates it when they have to rename a fileset to fit a new naming scheme. Instead of doing it the hard way and writing a one-time script to go through and rename everything, check out Bulk Rename Utility from [Jim Willsher]. It provides you with a multitude of methods to take care of business and allows you do pick your favorite method, be it regular expressions, simple finding and replacing, prefix/suffix modification, or a combination of many more.
However, if the sheer amount of options available overwhelms you or if you just want an easier way to do things, check out A.F.5 from [Alex Fauland]. A.F.5 offers features like adding a counter to your filenames, change file attributes, and save your rename settings out to a file for repeat use.