Ubfan1 may be correct; however, you can sometimes use my FixParts program to convert an existing partition from primary to logical without the backup-delete-repartition-restore dance. Be aware that you must not convert some partitions from primary to logical. Windows boot partitions are particularly risky for this type of operation.

Another possibility entirely is that you're running into rounding problems in the partitioning software. The libparted library (upon which Ubuntu's installer, GParted, parted, and various other tools rely) will try to round the start and end points of partitions to 1MiB boundaries by default. If existing partitions are not aligned in this way, libparted may try adjusting the specified start point, thus moving it into an overlap with an existing partition. The program then responds with an "unable to satisfy all constraints" message. The solution in this case is to create your partitions with small gaps between the new partition(s) and existing ones. A 1MiB gap should be sufficient, but it's conceivable you'll need a 2MiB gap. Creating partitions with another tool, such as fdisk or gdisk, may help, too. Be aware of the reasons for 1MiB alignment, though. I wrote this article on the subject some time ago. (An update is in the works, but hasn't yet been published.)