This had now resolved itself, but I am still left a bit baffled.
GRUB gives me the following three options:
Fedora Core 3 (2.6.9-1.667 smp)
Fedora Core 3-up (2.6.9-1.667)
If I go into the first one, I get the keyboard issue.
If I go into the second one, it goes straight through to the login, not showing the page which offers to run Kudzu if I hit a key within 30 seconds, the keyboard works and away I go.
I guess its a moot point, but I'd love to know what the difference between the two Fedora options are, and why FCore 3-up is the only accessible one by my keyboard.