Sounds like you talked to either a customer service rep that had no clue what they were doing, or were giving you a 'story'. Not shocking. I have run into companies that tell their reps to do their best to get out of doing certain things. Like unlocking a phone.
If you are referring to it being locked to that carrier/service provider that is. Call back and if the rep tells you they can't, or is unhelpful. Ask for their supervisor. I do, and then either they will somehow magically figure it out, or they will get you the supervisor who will either get it resolved or get you to someone who can resolve it.