Lion installed on my system with a custom MBR partition scheme (for EXT4 Linux + swap partition): it simply omitted the recovery partition, and never threw up any sort of error. Perhaps you GUID and MRB partition schemes are mis-aligned? (you can make sure they're in sync with REFIT or iPartition)