I am using 13.04 and I still can't search recursively with Nautilus 3.6.3. I also have NEMO and no issues with it.