What's interesting is that I signed us up for Tesco bank account but we were both rejected. Probably because we didn't have any history in UK yet but it still kind of sucked - now I am glad they rejected us. Ultimately the next day we went to red and blue US bank on the high street and got it all sorted within half an hour. We showed them contracts, documents and bills to our names (real estate agency through which we rent already sorted that out for us before we came) and we were done. Got our cards made at the spot as well.
So it was kind of the opposite for us. We could't get the bank account with Tesco because of their "security check" but could at the high street bank.