I had the same problem with Barclays (a long time ago...) when moving to the UK, they wouldn't accept a letter from my employer and they wouldn't accept a rental agreement either as proof of address. Solution: the confirmation letter that I received from the NI people was finally good enough, so I could open an account only a month after I'd moved to the UK! Btw. the NI number is a must anyway, so it's just that it takes some time until you get it.

This is a direct consequence of there being no official central registration of one's address in the UK, unlike in many other countries. You might call Austria bureaucratic for example, because you have to register within 3 days of moving (and another registration is necessary within 4 months), but then you get official papers that prove your address, so this never becomes an issue here, unlike in the UK.