Here is the link to a great file renaming utility that I use:
http://www.bulkrenameutility.co.uk/Main_Intro.php

It is free and powerful. It has a learning curve, but it’s worth it. It works great with Vista, too.
The main "boxes" I use are the replace box, which works just like a traditional search and replace, and the prefix box, which simply adds letters to the beginning of your filenames. You can also change the file extensions using the extension box:

The trick is to make sure you highlight the files you want to change the name for. A preview of the filename will automatically show up next to the original filename so you can check your results before you click the rename button.

Enjoy!