James,

man -k uses a keyword database. This database is generally updated nightly, though if this is a new machine, it may not have been made yet. As root, you'll want to run the command:

makewhatis

that should create the database if it is not there. Also, you can run this when you want to live update the database as well. For example, if you've installed some additional software, which includes man pages, the man pages won't be included in man -k until the following day [generally]. If you wanted them immediately searchable, you'd run a makewhatis.

-STM