LaraM, I had great US credit as well, but it just doesn't transfer over! I now have great UK credit (we recently went through mortgage applications and etc and DH and I were able to get approved with no trouble), but I've been here since 2008, so I've had longer to work at it.
I think a lot may depend on the bank you are with? For what it's worth, my HSBC account came with a credit card (with a very low limit) that has since been increased quite a bit. I got both at the same time when I went into the bank. I brought my husband with me, as he had business accounts at that branch and we got in to see a bank manager quite quickly, but we've never had a joint account.
The most significant jump for the credit card was when I got a job and suddenly had more cash! I've never had a phone contract here, just pay as you go, because I don't need one to get the phones I want, and it works out much cheaper. And we've always bought our cars used (with cash), so we've not needed loans there either. I've never bothered about the electoral roll, although I'm happy to be on it now as it means I got my UK citizenship!
Just like in the US, it's more of a steady and slow process without any one "thing" that magically makes your credit "worthy". Definitely go in person to your bank and see if they can work with you (they sometimes have more leeway than an online form would allow)... Maybe check out Tesco/John Lewis etc as well for their credit offerings.