I found the cause of the problem in my case. As part of the Maverick to Natty to Oneiric upgrade, something installed the xbindkeys package (xbindkeys-1.8.5-1). The file ~/.xbindkeysrc has definitions including:
c:41 + m:0x4
This unfortunately defines a Ctrl-f shortcut which has global scope (i.e. cuts across all applications) that starts an xterm.
I uninstalled xbindkeys, and of course its global Ctrl-f shortcut is now gone, thus enabling all of the application-specific Ctrl-f shortcuts, such as Ctrl-f for opening the search box in firefox, to work again.
I'm not sure why xbindkeys was installed during the Maverick-Natty-Oneiric upgrade. Anyway, I hope this bug report will help others who may encounter the same issue.
@Karl Ostmo, is xbindkeys installed on your system?