Currently nautilus only searches the current dir., recursive was added back right after the 3.6.1 release.
It could be added back in raring, maybe it will come in 3.6.?, maybe not.
(works quite well when enabled
https://bugs.launchpad.net/ubuntu/+s...s/+bug/1077415