Triple boot (Lion, Win7, Ubuntu) I currently have my MacBook Pro set up to dual boot OS X Lion and Windows 7. I am in the middle of a development project where I need to write some custom software that depends on proprietary drivers that only work in Linux. I have been using a vm but it's getting tedious. It would be nice to be able to boot up into Ubuntu natively.

Currently I have one 500 GB drive that has a 130 GB Windows 7 partition (bootcamp), Lion recovery partition, and my OS X Lion partition with the remaining space. When I try to partition the space i get "Partition failed, couldn't modify partition map because file system verification failed". 

I am doing this through Disk Utility running from a Lion recovery flash drive. First aid shows no errors on the drive, but I repaired it anyway and still I get the same error when I try to repartition. 

As a last effort I thought it might have to do with fragmentation of the free space so I defragged the drive (against my better judgment) using iDefrag, repeated the above process from USB recovery disk and still I get the same error.

What is the most efficient way to get 4 partitions: OS X, Lion recovery, Windows 7, Ubuntu Linux (booting using refit) without having to wipe everything and reload (reloading OS X and Windows 7 would be unpleasant)?
You should be able to use iPartition to solve this problem. I've had a lot of success with re-partitioning drives that failed when trying to use Disk Utility. It also depends on the partition scheme on the drive. If the scheme doesn't support repartitioning you will have to wipe the drive and start fresh.

I would suggest a GUID partition scheme.