Gah, "it just works" was not quite the case this time but I got it to work! I have an early 2008 Mac Pro with a RAID array and OS X 10.6.6. I downloaded Lion and got the infamously vague error message. I then tried the following in not necessarily this order:
1) First I tried zapping the PRAM by holding down command-option-P-R all at once during startup. Nothing happened. Then I remembered tip #1: For some reason, at least on my Mac, the keyboard only works during startup if plugged into the front of my mac, not if it is plugged into my monitor. This time I got two startup chimes like I'm supposed to, showing it was indeed zapped. Anyway, still didn't help.
2) Then I tried running disk utility from my installation disk and sure enough there were some problems with the disk which it fixed. Still didn't help Lion get installed.
3) I followed the nice instructions on how to burn your own Lion installation disk at: http://mashable.com/2011/07/20/lion-clean-install-guide/#20859Step-1-Download-Li on-From-the-Mac-App-Store
When I ran the install disk from the resulting installation disk I still got failure but this time it took the form of the installer freezing up during a "checking disk" message. Sigh...
4) I checked the hardware requirements but a Xeon Mac Pro is indeed Lion material.
5) On the theory that maybe the RAID array was causing problems, I used the Lion installation disk to undo the RAID (after a full backup!) and then redid it using its disk utility. Still no good. And Mail crashes now. Sigh.
6) Started looking up prices for new Macs and getting sticker shock.
7) Suddenly inspiration! The "checking disks" error caused me to remember reading something once about external firewire disks causing problems. I unplugged my WD external firewire disk drive (that I use for TimeVault backups) and tried again with my Lion installation disk. Success! 🙂
Anyway, hope my bedraggled saga will be helpful to someone.