Eu tive um problema semelhante no meu MBP13 final de 2009. O que eu fiz foi arrancar a partir de um backup inicializável que eu tinha em um disco rígido USB externo. Então eu poderia mudar o dispositivo de boot primário para o meu drive de DVD e reinstalar o Leopard (e iniciar o processo de atualização para o Lion yay!).
Observação: você deve usar os discos de instalação que acompanham o seu Mac, e não os discos de atualização.
Você também pode tentar arrancar a partir do disco de instalação, eu sei que você disse que não funcionou, mas por favor tente. Eu tive que esperar por 5 minutos uma vez.