Just wanted to say... DH and I arrived in the UK on Thursday (15 Jan.). We went into Royal Bank of Scotland on Friday and they told us they could only let us open an account with a utility bill. A tenancy agreement wouldn't be acceptable, nor would a cell phone bill.
We then went into Barclay's last night and told them our situation, and they agreed to open an account with just a tenancy agreement (and passports/licenses, obviously). We opened a premium account with them today (which, for 25 quid a month we think is well worth it; it insures all of our electronics including mobile phones, we have travel insurance, identity theft protection, online banking, debit cards, and a host of other cool features).
Just wanted to share my experience for people moving over in the future.