I had this happen to my Feb2011 13" MacBook Pro running the latest Lion OS.
After running several utilities on the partition I was still unable to get it to boot, without experiencing the Kernel Panic immediately after seeing the Apple logo screen.
I didn't want to reinstall Lion, because I didn't want to go through the process of having to reinstall all my apps etc.
Here's what I did to fix my problem. Fortunately this worked on the first try, and no ill affects have been seen since.
1 - from a different computer running the same OS as the one that is corrupt, go to Apple Support site, download latest Combined Update installer
3 - start corrupt Mac in Target Disk Mode
4 - attach corrupt Mac to secondary Mac with a firewire cable
5 - on secondary Mac run Combined Updater, be sure to change installation location when prompted to your externally attached corrupt Mac
6 - once installation is complete, eject hard drive of corrupt Mac.
7 - power down corrupt Mac and then attempt to power it up.
This method may or may not work depending on whether the file(s) which were corrupt/erased as part of the failed update are replaced as part of the OS Combined Update installation.
Good luck!!!!!!