I've had loads of problems with this and related issues but eventually sorted them all. Here is an account of what I did - I hope it helps someone!
Tried to install Lion – got message “recovery partition couldn’t be created”
Tried reducing size of partition on boot drive – didn’t work.
Tried deleting files on boot drive to make more space – didn’t work. Did complete Time Machine backup onto external drive.
Installed Lion on external drive – booted from that – worked fine.
Having booted from external drive, took a deep breath and partitioned boot drive (and thereby erased all data!).
Discovered I'd deleted the Lion install program (!). Tried to re-install from within Lion but wouldn’t work (despite holding Option key when clicking on the install icon).
Inserted Snow Leopard install disk; changed start-up disk to superdrive and rebooted with Snow Leopard (with install disk in the drive).
Re-downloaded Lion installer from App store.
Ran installer to install Lion onto boot drive – had to change username but worked fine.
Launched Migration Assistant and restored whole system from Time Machine backup. Left it running overnight; worked fine.
Couldn’t work out why I couldn’t see original files and applications; realised I needed to log off and log back in using new username!
Hey presto everything working fine – until I tried to run Mail. All my old messages were imported when the program launched but the program would not run.
Eventually solved by moving everything in the Library/Mail folder to another folder (could be desktop or anywhere) and relaunching Mail. Program then ran fine but no old messages there.
Old messages and mailboxes had to be imported one by one (using File/Import) from where I'd moved them. Everything fine with Mail after that.
Found I couldn’t launch iTunes (“…library was created with a newer version of iTunes”). Solved by finding Library.itl in the iTunes library folder. Renamed it to something else. Located latest iTunes library file (in Old Library folder) and renamed it Library.itl (this effectively allows you to downgrade to the previous version of iTunes you were using).
iTunes then ran fine and loaded up latest library.
Only problem now is I can't update iTunes. Not a problem for now. I gather Apple are looking at this.
Andrew