Bain may well be correct, but the description of the Linux tool showing the disk as unpartitioned makes me think that something else may be going on. Specifically, I suspect that the disk may be using the Master Boot Record (MBR) partitioning system, but with leftover GUID Partition Table (GPT) data from a previous setup on the disk. This type of configuration is known to give the Ubuntu installer fits. If I'm right, the solution is to clear away the old GPT data. One easy way to do this is to use FixParts, as described here.
Before deciding what to do, I recommend posting the output of the following command, typed at an emergency Linux boot's command prompt:
sudo gdisk -l /dev/sda
If it tells you that it's found both MBR and GPT data and asks which to use, then my hypothesis is correct and you should use FixParts (or some other tool) to delete the old GPT data. If it doesn't present such a question, though, it could be that something else is going on -- maybe a simple Basic/Dynamic problem that's showing unusual symptoms, or maybe something else. Also, it's entirely possible that both issues are in play -- you could have leftover GPT data and a Basic/Dynamic problem!