When troubleshooting various aspects of OS X and Mac hardware, one common routine is to boot into Safe Mode to automatically run some maintenance routines and prevent the system from loading inessential features. This can be done by holding the Shift Key immediately after hearing the boot chimes when starting the system up; however, sometimes this may not work.
Booting to Safe Mode requires the Mac's firmware to send the kernel some variables (boot arguments) that it interprets as a command to modify the procedures it uses to load the rest of the system. These can be set manually by going to the Terminal and entering the following command:
sudo nvram boot-args="-x"
To undo this, enter the following:
sudo nvram boot-args=""
Generally, the Shift key is held down the firmware will pass the "-x" argument to the kernel so it loads into Safe Mode, but if it's not doing this then either the firmware is not working properly (or is locked), or--more likely--your keyboard is not working properly.
If the firmware is locked (has a firmware password set) then you will not be able to send the kernel any boot arguments. One quick way to see if the kernel has a password set is to boot with the Option key held down, which should bring you to the boot manager screen where you can select a boot drive. If the screen loads then you do not have a firmware password set up; if the system prompts you for a password then the firmware is locked with a password.
To remove the password, you can either change the system's internal hardware configuration (remove or add RAM), or boot from the OS X installation DVD and choose the firmware password utility from the Utilities menu.
Testing the keyboard
Try plugging your keyboard into another USB slot, or try using another keyboard altogether. In addition, try removing all USB devices except for the keyboard and mouse, and try various keyboards again. Both Windows and Mac keyboards should work the same, but if you are having troubles you might consider avoiding wireless keyboards and sticking with a basic wired option while troubleshooting.
Testing the NVRAM/PRAM
If the system's parameter RAM (PRAM) is not working then it may be passing the system some firmware settings that could be conflicting with those coming from the keyboard. Try resetting the PRAM by rebooting the system with the Option-Command-P-R keys held down. Keep these keys held while the system resets a few times, and then release them to allow the system to boot normally.
In addition to resetting the PRAM, try using the commands mentioned above to manually set the firmware variables for booting the system into Safe Mode. If these work then the PRAM is working properly.
Testing the kernel
One final option could be if the system kernel is somehow corrupt and not accepting the boot arguments being sent to it. While reinstalling the OS from the installation DVD should replace the kernel, you might first try installing a fresh copy of OS X on a secondary boot drive and booting off of that. If that drive will boot into Safe Mode when the Shift key is held down, then the firmware and hardware are working properly, and the issue is with the kernel and perhaps other aspects of the filesystem.
Some filesystem setups have boot helper partitions on them that cache boot loader and extensions to help the system boot. In these instances if a full reinstall does not work, you might consider fully partitioning the drive and setting up the filesystem again. To prevent loss in workflow while doing this you can clone the boot drive to an external volume and run off that while you use Disk Utility to rebuild the main boot drive.