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 (note that unfortunately Emacs uses a different syntax than PCRE).
For example, to rename files with counter (starting by 1):
M-x replace-regexp (that is Alt+x followed by the string "replace-regexp" typed in the minibuffer at the bottom of the screen).
\,(format "P%04d.jpg" (1 + \#))
To reuse a counter in the filename:
\,(format "P%04d.jpg" (string-to-number \1))
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)