if that fails,

Take the OS X installation disk and do an Erase and Install on that disk.

Then try again with the Time Machine restore.

P