Find install disk that matches the current MacOS
I ran into this same issue when trying to boot from the original install disk that came with my MacBook Pro 15" non-unibody. After the gray apple screen I got scrambled unreadable screen, like the screen was sliced diagonally and each segment shifted.
The OS is upgraded to Snow Leopard, using the Snow Leopard install disk as the boot DVD it was fine, and I was able to do what I needed (run Disk Utility to clone the drive).
I know this might not help you to restore to factory settings. My guess is with the major system updates, a firmware tweak may have made it problematic to now use the original install disk.
Some things I thought to try but didn't, that might work?:
Set screen resolution to something low then boot from DVD.
Reset PRAM right before booting from DVD.