I had the same errors in my mid-2009 13" MacBook Pro. I had upgraded my machine to 8GB (2x4GB) of memory instead of the standard 2GB.
Apparently Lion didn't like this, and I'd get a kernel panic almost every single time I tried to install/run Lion.
I took out one stick, and everything worked perfectly. No panics. Tried using the other stick (to check if it was bad) and it also worked perfectly. Finally, I put both in to see what would happen (now that Lion had been safely installed) and everything seemed okay. I ran a memory test with TechTool Pro and it reported no errors with my memory. Unfortunately, the kernel panics started up again, so I took it out.
Tried again with my two old 1GB sticks and they worked perfectly, but when combined with any combination with a 4GB stick, the kernel panics would start again.
I'm not sure what exactly is going on, but I know my machine is stable so long as there's 4GB of memory or less in my machine. Hopefully my hardware isn't bad, and it's a software issue.
stripedsnake, try taking out a stick and see if it works.
Anybody else have this issue?