Triple boot (Lion, Win7, Ubuntu)
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.