Someone so lied to you. Word of advice, never listen to the first phone rep who says something can't be done. Unless they actually tried to do it. I was always getting flack from supervisors when I was one because I wouldn't tell customers stuff that just wasn't true.
No one else can unlock it for you. The only place that can unlock the phone is the carrier/service provider. I would call them again and when you are told it can't be done, ask for a supervisor. And don't let them tell you they can't get you one either. It is best to call earlier in the day too. Due to the fact that more in house staff is around then. Later at night or in the evening you may get remote staff.
BTW They are required to unlock it for you if it is paid off...