Windows installation: Couldn't create a new partition or locate an existing one

Apparently my specific BIOS version simply did not allow OS installation through USB:

Serial ATA AHCI BIOS, Version iSrc 1.20E
Copyright (c) 2003-2008 Intel Corporation
**This version supports only Hard Disk and CDROM disks.**
Please wait. This will take few seconds.

This would appear for about 0,5 sec during the boot sequence.

I found an old Windows 7 CDRom and it's installing without issues now.

I had the same error installing windows 2012 server R2 in a Dell R210 II. My machine didn't give me a message saying it wouldn't support USB, but I tried practically everything that the OP did to no success. I checked the log %WINDIR%\Panther\setuperr.log and had the message:

Error [0x06069e] IBS GetMachineInfo:Couldn't find boot disk on this BIOS-based computer

I came across a webpage that said the windows installation had problems because it was using USB3.0 and I should try an older USB. I did that too and it didn't work, but it got me in the right track. I booted a CD with grub and booted the USB from there, finally it worked. Here's what I did once I got GRUB loaded:

c # to access the command line
root (hd1,0) # hd1 is the USB stick
chainloader +1
boot

This fooled the windows installer, because I was no longer booting from the USB, I was booting from a CD instead, even though the installer was loaded from the USB. I hope this helps other people.

I had the same problem until I used USB 2.0 drive which worked... I used 3.0 before and tried everything without luck. USB 2.0 FIXED this problem.