I must say, you have 'shrunk' a lot.
Your problem with Ubuntu not installing was probably becuase you did not create space for Ubuntu. Ubuntu's installer must see either EXT4/Linux filesystem or just 'unallocated space'. Ubuntu will NOT install on NTFS.
When installing two versions of Windows, it is a good idea to install the older Windows version first, that is you did the right thing by installing Windows 7 then Win8. However, I must ask , why do you need two versions of Windows?
Anyways, to install Ubuntu and other OS, format and create your partitions on HDD in advance.
Here's what I'd do if I were you:
Install Windows FIRST. You can tell windows installer where to install each Windows.
100GB NTFS PRIMARY Windows7 C:
100GB NTFS PRIMARY Windows8 C:
300GB NTFS PRIMARY Windows D: [for both Win7 and Win8, also this can be shared with Ubuntu]
25GB EXT4 LOGICAL Ubuntu / [for ubuntu system files]
25GB EXT4 LOGICAL Free
443GB EXT4 LOGICAL /home or just 'free' for linux DATA.
Install Ubuntu. Use 'Something Else' option to manually guide your Ubuntu installation.
Select the first 25GB Parition, check Format, Use as= Ext4, Mountpoint=/
If you want to use the 443GB partition as /home then use Mountpoint=/home, use as=Ext4.
You can use Gparted from the Ubuntu DVD/USB to setup your partitions. When installing Windows reformat the partitions as NTFS with Windows installer, and like wise reformat EXT4 partition with Ubuntu installer.
EDIT: No you don't need UEFI.