I'd try this:

Open excel
test ctrl-F to see if it works (just in case)
if it doesn't work, hit alt-f11 to get to the VBE
hit ctrl-g to see the immediate window
type this and hit enter:
application.OnKey "^f"

Maybe there's a macro that's trying to steal that shortcut key--or just trying
to kill it.

You can use these two sites to try to find that macro:

Chip Pearson has some notes on how to diagnose startup errors:
http://www.cpearson.com/excel/StartupErrors.htm

And Jan Karel Pieterse has more notes:
http://www.jkp-ads.com/Articles/StartupProblems.asp

ps.  While you're working on the solution, remind the user that ctrl-h will
bring up the Edit|Replace dialog and you can click on the find tab.