Ok i have just solved the problem.
I wanted to install Lion on my iMac 27 which had 6 partitions: EFI, Mac (HFS+), Storage (NTFS), Windows (NTFS), Linux root (ext4) and Swap in a triple-boot configuration all managed by reFit. Lion installer was giving me the same error as many of you are having "This disk cannot be used to start up your computer." I tried to resize Mac partition with Disk Utility with no luck because i got the already commented error message "Partition failed: Mediakit reports no such partition" and some other annoying errors trying to delete or resize, repair or check for errors on the rest of the partitions. Uninstalling reFit was ok but didn't help to get the installer working. I tried to use Disk Utility booting from Lion boot DVD and nothing. But after all of that i found the solution.
To get it working i used an Ubuntu 9.04 LiveCD, booted the iMac with it (Pressing and holding Alt key after the "Gong" sound), used Safe Graphics Mode to boot because graphic card didnt work well on Ubuntu (Press F4 in ubuntu LiveCD first screen). When Ubuntu was fully loaded i opened GParted (Partition Editor with GUI included in Ubuntu) and first of all i deactivated the Swap partition to been able to delete it, after that i deleted Windows and Linux root partition, leaving unused space unformatted (I was planning to format it later with HFS+ on Snow Leopard) , the only partitions i left untouched were EFI, Mac (HFS+) and Storage (NTFS). Quit Ubuntu an rebooted iMac, login in Snow Leopard, run to execute the Lion installer, no luck, went to Disk Utility, reduced size of Mac partition, executed Lion installer again and the magic appeared ¡¡¡NOW I CAN INSTALL LION!!! Went again to Disk Utility to leave the partition as it was after the resizing, went again to Lion installer and worked again.
I hope this helps.
By the way, i installed Lion with no problems on my MacBookPro which has the same partition scheme (reFit for triple-boot included) as my iMac except for the Storage partition which its file system is HFS+ instead of NTFS. I didn't have to delete partitions or do some weird stuff, just launched the Lion installer the first time and worked like a charm including reFit which it's still present at boot for selecting the OS i want to boot.