I reported this on Launchpad [1] and was forwarded upstream.

Steps to reproduce:
1. touch ~/foo_åäö
2. In Nautilus, point at the file created in step 1
3. Right-click for context menu
4. Select Move to Trash
5. Press Ctrl-Z/Select Undo from the Edit menu

What happens:
Nothing

What I expect to happen:
For the file to recover from trash to ~.

What works:
* Undoing Move to Trash with files with no scandinavian letters in their path/filename.
* Recovering foo_åäö by opening Trash and selecting Recover from context menu.

More info:
* Could be that more characters, perhaps all non-ASCII characters render Nautilus’ Undo impotent — I’ve only tested å, ä and ö.
* The Finnish translation for Desktop (~/Desktop) is Työpöytä, which means files moved to trash from Desktop can’t be recovered. Nasty.

*[1] https://bugs.launchpad.net/ubuntu/+source/nautilus/+bug/973620