Comment 3 for bug 1140872

As the nautilus bug is still open and has had no attention, here is a workaround:

Install the Nautilus-Actions Configuration Tool, create a new action and in the Command tab set the path to /usr/share/nautilus-renamer/nautilus-renamer.py and the parameters to %U (a space separated list of the file/folder URIs which correctly encodes spaces as "%20" instead of "0")