I’ve heard a few bad things about NatWest, lately, which is bizarre because some of their branches (including mine!) have accepted deeds poll made by my tool without complaint. Suggest that you get government ID (e.g. passport, driving license) changed first, then go back to your bank with your new photographic government ID and explain to them that if you were to open a NEW bank account in your new name, then they’d let you… so why won’t they let you change the name on your existing account?
If they still cause trouble, ask to speak to the branch manager and re-explain the situation. Point out that every other bank on the high street would be more than happy to open an account for you in the name that now appears on your driving license, passport, bills etc., and ask if he or she would prefer that you bank with them, instead. Then, in the unlikely event that they haven’t seen sense – go elsewhere: you don’t want to be banking with somebody who doesn’t understand your rights as a British citizen anyway.
You might also like to show them this article from the Guardian, for which a representative of NatWest stated on the record that deeds poll created by freedeedpoll.org.uk were acceptable.