Let me try to explain this one.
Problem: If you already have four primary partitions, then you won't be able to create another partition on your hard disk.
Solution: Copy all the data from one of your partitions to another and delete that former partition. You can copy it to an external hard disk too. I seriously can't see any workaround for this.
In order to delete a partition, launch Gparted and right-click on the drive that you wish to delete. Refer to the figure below:
After deleting it proceed with inserting a Live CD and your ubuntu installation. When you reach the step that you have shown in the figure, select the "unallocated space" (We will have that since we just deleted a partition) and select "logical" from the small window that pops up.
I think you can complete the rest of the installation steps with your own logic. Do let me know if you need any more information. :)
You can see my logical partition as /dev/sda2. Once you have a logical partition, you can create as many individual partitions in it as you want. As for what's the exact difference between a primary and logical partition, I'm afraid I do not know.