This is normal - you won't be able to take out a phone contract until you have some UK credit, because they run a UK credit check on you first before you can be approved for a contract.
As you have just moved to the UK, you won't have any UK credit yet (your US credit is irrelevant), so you will have trouble with getting phone contracts for the first few months. Your credit score is linked to your UK address, so you will need to wait until you have credit at your current address first, before you can get a contract.
Best thing to do (and possibly the only thing you can do) is to buy a cheap phone and start off with Pay-As-You-Go, then try for a contract phone in a few months or a year or two.
You can get some good deals on calls, texts and data with Pay-As-You-Go, so it can be a pretty good option, especially if you won't be using your phones much.