Job hunting is horrible. You just have to keep trying and one day the chance will come along and you can prove the 'rejectors' wrong!

Banks are strange creatures. Barclays didn't want Rose when she applied for an account while on a Fianceé visa, but Nationwide did with no issues. Barclays lose out now since she's earning. The only problem is that Nationwide don't seem to offer contactless cards, I use the feature all the time on my credit and debit cards.

Rose took a mobile contract soon after arriving, she went on a monthly with Vodafone. They wanted a £50 deposit (credit) on her account. However she got terrible service and left after around 6 months and went Gifgaf PAYG, much better. Still, she got the statements etc. which all helped.

Building up a credit record is hard to start with. But it should be possible over time to get things like a credit card with a low limit (once you have a account for say 6 months your bank or building society should have an option for you).