For a BIOS machine, the most compatible and simplest solution is to use a MBR formatted disk. GPT may have worked, but it’s a hit-and-miss and I don’t think it’s worth the trouble. Booting from a GPT drive is geared more for towards a (U)EFI system.
You say you don’t mind re-installing - This time, ensure the drive in GParted has a new partition table set as msdos (MBR). You may wish to consider setting up an extended partition so you can have more than 4 partitions. Ubuntu will happily boot from a logical partition. 
It is possible to do a GPT to MBR conversion without data loss, but it’s probably best to start clean since you wouldn’t need a “BIOS Boot Partition” for a MBR drive in a BIOS machine… and the fact it doesn’t have a working bootloader.
Some further reading:
- Legacy BIOS Issues with GPT: http://www.rodsbooks.com/gdisk/bios.html