If possible, try/borrow a SIM card from another provider. It's known that some providers in the UK "blocking" the update. Be sure that besides a mobile connection, you also have a Wifi connection to download.
No, has noting to do with a locked phone. Just the SIM provider you're connected with. Most people have problem with EE and 'friends'.
Only removing doesn't do the trick. You need to be connected to a provider.
Read this threats:
I live in the Netherlands so i don't know about the UK providers, only what I read on different fora. Again, it's probably not the phone, but the provider.