The only time I can remember getting this error, the path and filename became too long.
Note: PM uses an intermediate filename to assist in renaming (and to ensure uniqueness), and it was this intermediate path+filename that was too long. Funny thing was, PM could not even rename the files back to their original names (something that it nicely does if it fails). Once the names had become too long, Windows plain refused to do anything with them (not even manually or on the command-line), you can't even open them anymore! The solution was to rename a directory on the path to something smaller and the rename the offending files. Phew...
Another thing that may cause rename to fail, of course is that you do not have enough permissions to do so.
Hope this helps,
Hayo