Same problem here...but with a little better luck. Loaded the Leopard DVD, click restart to start the installation process, machine restarted but got stuck on the gray screen with the apple logo and the clock whirling not stop. Left it there for like 15 minutes and then hard restart (pressing power button for 6 seconds) and pressed the button mouse to eject DVD. Fortunately my machine restarted on previous system (10.4.11) with no problems.
Maybe the restart with the Leopard install DVD takes longer than normal, but I chose to restart because the disk was not even spinning (no reading/writing from it) any more. How long should one wait, or how long is long enough?
Sorry I didn't help with your problem, but we're in the same boat and maybe somebody can rescue us with some ingenious tip(s).