I reported this on Launchpad  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 I expect to happen:
For the file to recover from trash to ~.
* 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.
* 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.