In reply to Shearwater:
> Sounds like its a UEFI bootloader security wossname. The boot sequence is demanding a signed OS boot image... stuff like Windows 8 provides that, but Linux generally will not.
Yep, sounds about right. Disabling secure-boot should see you right.
One other potential problem that may be a concern if the machine has had Windows on it in the past is that the EFI partition can be locked as well. The only way I have found to get round that is to back up anything that is in it elsewhere and reformat the partition from your Live CD before transferring the backed-up stuff back into it. However, if the computer is genuinely lacking an OS and has never had one, I don't think this should be an issue