I had the exact same issue after installing the latest firmware.
Garmin software support instructed me to reload the latest maps. That must have caused the ASR files to get rebuilt. After that, the "Find by Name" and "Find Address" voice commands worked again.
So, if you're having this problem, I'd suggest re-installing your latest set of maps. It fixed it for me!