How can I fix an Install Failed error while installing Lion?

Question

I downloaded the new OS X Lion from the App store. I am running the latest Snow Leopard on my 2010 15" Macbook Pro. During the download, it somehow stopped while I was away from the keyboard. When I returned, I resumed it again, and after download completion, began to install it.

When it rebooted, it began to install Lion, and when it was at the 33 minute mark, it failed.

See pictures below:

I got the error message:

Install Failed

Mac OS X could not be installed on your computer

Mac OS X couldn't be installed, because the disk Macintosh HD is damaged and can't be repaired.

I read somewhere that I should put in the original install DVD, and run the Disk Utility to try to verify and repair.

I put the disc in, booted it, and clicked through past the language selection, but made sure to wait for the top menu bar to appear to get to Disk Utility. I clicked on Verify Disk, and got this error message after it ran:

Invalid node structure

The volume Macintosh HD could not be verified completely.

Error: This disk needs to be repaired. Click Repair Disk.

After clicking Repair Disk, I got this error message:

Disk Utility stopped repairing "Macintosh HD"

Disk Utility can't repair this disk. Back up as many of your files as possible, reformat the disk, and restore your backed up files.

I'm also running Bootcamp, with Windows 7 installed in it's own partition. I don't know if that has anything to do with why I'm getting these error messages or not, or if that's why it thinks the hard drive is damaged.

How do I fix this?

I am unable to get back into Snow Leopard. Every restart leads back into the Lion install, which results in these errors. I think many others are having this issue as well.

I do have my files backed up (not in Time Machine, but manually on an external USB drive). I don't mind wiping everything (including Bootcamp), but I rather that be a last resort.

Reference:

• Install Failed - Disk is damaged on Apple Discussions site.