How can I fix an Install Failed error while installing Lion?
I ended up bringing my Macbook Pro into the Apple store. The genius there attached the store's OS X Snow Leopard via USB, and booted from it, and ran the Repair Disk, which gave the same error of an invalid node structure. Since it was still under Apple Care, I got my hard drive replaced and was able to keep the old one.

With the new hard drive, it had Snow Leopard on it, and I simply upgraded it to Lion without a problem. I was able to attach the old hard drive via USB, and restore all my files.

Thanks everyone for their help. +1 to everyone.