we couldn't create a new partition or locate an existing one
I got this error over the weekend while trying to upgrade one of my computers to Windows 10. I was using a bootable USB built with the Media Creation Tool.
Everything started up fine, but when I tried to install Windows 10 on a specified partition, I got an error: we couldn't create a new partition or locate an existing one".
It turns out, Windows tries to create a few partitions on the primary hard drive (the one you booted from) to support the installation of Windows. However, the installer won't create said partitions on a removable device - which is what I had set as my primary boot device.
To solve this issue, I removed all of the boot devices - except my hard drive - from the BIOS menu and restarted. As my computer was rebooting, I loaded the quick boot menu and selected my USB device. After that, I was able to install Windows like normal.