OS X Lion Repair Permissions breaks disk?

I'm running on a new (less than 2 months old) 27" iMac with OS X Lion installed.

Safari crashed on me a couple times last night, and since that's unusual I decided to run Repair Permissions. The process generated a very long list of repaired file permissions followed by the message that the permissions were repaired.

So I launched Safari again, did a Google search, and Safari crashed... again. So I decided to run Verify Disk, which promptly told me that the disk needs to be repaired. No problem -- so I rebooted into Lion Recovery, launched Disk Utility... and was promply told the disk has an invalid key length and could not be repaired and that I need to format my hard drive and restore from backup.

Okay, so far just a big inconvenience, but not a problem. Since I have a current Time Machine backup, I formatted the disk and began the process to Restore from Time Machine Backup. Three hours later, my Mac was restored. All seemed good, but I was curious, so I launched Disk Utility and ran Verify Disk. To my delight, I received the green message that the disk was healthy! So far, so good. So I decided to run Repair Permissions again, since there were so many permissions repaired last time, and I figured all those wrong permissions were probably on my backup as well. This time, the repair failed; a permission could not be fixed. So I decided to run Verify Disk again, and was promptly told the disk needed to be repaired... again.

So it's now starting to sound like I have a bad hard drive. I checked my serial number against Apple's database of iMacs that received a bad Seagate hard drive, but was informed my machine was not one of the affected models. Is there anything else I can try, or should I just have the hard drive replaced?