I had a similar problem with my macbook. Try getting Onyx, because that's what i did and it told me to reboot and press some keys and access disk utility from there, and do the same repair disk thingy and that's when it worked!
Sorry cant remember what you have to press when u reboot !
EDIT: When you reboot hold Command + R, which will take you into Lion recovery disk assistant or something and access disk utility from there to repair your disk
I'm guessing Onyx said to hold option, boot from Lion's recovery disk, and use that Disk Utility to repair your boot disk - repairing permissions from a disk other than the one you're running seems to help sometimes.