Interesting...
By any chance did you or someone else ever set up an EFI firmware password on this system? It could explain why your system won't boot from the optical drive when the Install DVD is inserted since many of those snag key features are disabled when the EFI firmware password is enabled. It would most commonly be used in a school environment. Here's more information on the firmware password:
http://support.apple.com/kb/HT1352
If you have an EFI firmware password and can't remember it you'll need to reset it before continuing. A quick Google search will turn up methods for performing a reset.
If you don't have an EFI password set try this. Instead of holding down the 'C' key, hold down the option key instead to load the system picker. Make sure the Install DVD is in the optical drive. Does the Install DVD appear as one of the boot options? It may take a minute for it to appear once the hard drive icon appears. If the Install DVD never shows up, and you don't hear the optical drive making any noise then you may have an optical drive problem too.