I know that sometimes upgrading rather than re-installing can cause issues, especially when done multiple times. It's possible that some dependencies have been messed up, or you have improper versions of some packages installed. There's a boatload of things it could be.
Your best bet would probably just be to re-install and start fresh. I'm sure there are other solutions, but that's probably the easiest, and will yield the best results.
ok, so I downloaded the 11.04 iso 64 AMD, made the disk tried to boot from it and got the same thing:
well I took a picture but I have no idea how to upload it so....fail