yo tengo uno de orange y es libre... lo probé con movistar y funciona.
creo que lo que pasa es que el que te lo dijo, no sabía configurar los APNs de otro operador y por eso puede que no fuese la conexión, pero aún así el resto debería funcionar.
de hecho, si no me equivoco, cuando probé el mío con movistar, creo que cogió automáticamente los APNs de movistar, pero no lo recuerdo con exactitud.
Suerte y saludos.