Just thought I'd throw this one into the ring:

Lupas Rename
http://rename.lupasfreeware.org/lupasrename.php

From this page:
Lupas Rename is a FREEWARE program developed to rename a big number of files.
It works on Win95, Win98, WinME, WinNT, Win2K and WinXP.
It is a simple .EXE file and doesn't need any other external libraries.
==========

I'm not running Vista, so I don't now how it'll behave here.

Granted the last release was 2005-04-01...

It's has a very comprehensive set of rename functions, supports audio and EXIF tags, good depth for renumbering, and a clear and concise interface.