If you are familiar with Emacs, I think nothing beats Dired for this task. Even if you don't use Emacs that often you may find Dired a handy tool.
sudo aptitude install emacs23-nox
Start Emacs Dired mode for a directory:
emacs -nw path/to/dir/
Now enter edit directory mode:
C-x C-q (that is Ctrl+x followed by Ctrl+q)
You can now edit the filenames like editing text in every plain text editor. You may even chose to replace the filenames using regular expressions.
When finished, type:
C-c C-c (that is Ctrl+c followed by Ctrl+c)
Or alternatively press the following sequence to abort your changes:
C-c Esc (that is Ctrl+c followed by Esc)