Help! Invalid index key

iMac i3 with lion. I started having some shut downs with a kernel error which looked like it was related to parrelells. My wired memory was stuck at 9.5 gb out of 12 gb. Eventually my Mac would not boot. I booted out of recovery hd and ran disk utility

"invalid index key" the volume iMac hd was found corrupt and needs to be repaired. Error: this disk needs to be repaired. Click repair disc

I did the above and it lists "invalid index key"
Rebuilding catalog B tree
The volume iMac hd could not be repaired
Volume repair complete
Updating boot support partitions for the volume as required
Error: disk utility can't repair this disk. Back up as may files as possible, reformat the Disk, and restore your backed up files

Is this from a software issue, virus on my parrellels or Mac, or hardware issue?

Any other steps to try?
I have apple care, is something like this covered?

Any ideas would be helpful

Thanks

It sounds like it might be a problem with your hard drive. If possible, backup all your data using Time Machine or some other means, use Disk Utility to reformat the drive and check it again. If you get the same error and your machine is still covered by Apple care, make an appointment with Apple to have the hard drive changed out.

Another option is to buy Disk Warrior and use it to repair the disk. No guaranty that it will be able to but it's lot more powerful than Disk Utility.

Ok thanks for the reply. I have a time machine backup, so via utility, I attempted to reinstall Mac os x lion but my Mac hd did not show up as an option for the install drive so I assume I was in the wrong area and backed out

I am not sure where to go from here. In a boot up from a USB, in utilities, it only gives me 4 choices. Restore from time machine, reinstall Mac os, get help, and disk utility. The reinstall Mac os appears to be loading the os on to a partition drive vs mymmac hd drive, the larger portion.

How do I reformat the drive and reinstall from here?

Disk Warrior would fix that, but it could also be the sign of a failing hard drive.

Time Machine cannot "just install Lion." It does selective restore of individual files and folders, or does a complete restore of the entire drive.