The boot sector of the drive is fine or you'd never get to the gray/blue screen.
fligex is correct in the fact that a sector or two may be corrupted. Most of the time you can run "repair permissions" and "Repair Disk" with disk utility and it will fix the problem. Unless the drive is just dieing then the problem will come back or it just will not boot again.
This is why you need to boot from install DVD, another Mac or and external drive with OSX installed.
You cannot seem to get the install DVD to boot. Unless you take it to an Authorized Apple repair you are just going to be in limbo until you can get one of the above listed to work.
Did you ever get the DVD out of the drive?
I can only offer the same suggestions from before, I'll give them again just for grins.
1. The install DVD (a gray dvd) has to be the same DVD that was shipped with that Mac. Unless you have a retail DVD (a black DVD) in which can see OSX on that disk cannot be older than the OSX that shipped with the Mac. If these are not followed then the Mac may not boot from the DVD.
2.Sometime you PRAM and or SMC can get into a state that needs to be reset. They can cause many sporadic problems and the Mac not booting is one of them, and the Mac not ejecting the DVD is another. This is why it is important to make sure that they get reset, and properly.
Pram:
http://support.apple.com/kb/HT1379
SMC:
http://support.apple.com/kb/HT1411
3. You can boot from an external drive that has OSX install, by the following.
Plug the external drive into the Mac, then power on the Mac and immediately press and hold the "option" key until the Startup Manager appears. Select the external drive from the GUI interface and press the right arrow button on the lower right bottom of the screen. This will force the Mac to boot from that drive. At this point you can run disk utilities from the external firewire drive against the internal Mac drive.
4. You can also put your Mac (with the disk install) into Target Disk Mode. Then plug the TDM Mac into another Mac with a firewire cable. Then TDM will populate on the desktop of the other Mac as an external firewire drive at which point you can run the disk utilities against the external (TDM Mac).
5. Since you had the drive out you could easily put it into an external enclosure and plug it into another Mac to run the disk utilities against it.
Good luck...