the biggest reason for not getting credit is not being on Voters Role.
When we moved last time, we purchased our house for cash (�126,000) and we couldn't get British Gas to change over from a prepayment meter to a normal meter as we weren't a good credit risk!
Get yourself put on Voters Role and you should not have a problem - though it may be worth getting an up to date credit check done
http://www.experian.co.uk http://www.callcredit.co.uk and htt://www.equifax.co.uk