iPhone 4S activation problem

[GuiRampon]

Hello! My father was a Verizon Wireless customer for years while he lived in the USA. Last month, he moved back to Brazil with his Apple iPhone 4S after the company he works for paid his contract cancellation fee, which would make it possible to use in another carrier. In Brazil, we are having problems activating his iPhone in the new carrier (VIVO). The iPhone recognizes the service, since it starts the activation process in VIVO's 3G network, but it displays a message saying the SIM card is invalid. "The SIM card inserted in this iPhone does not appear to be supported.  The SIM card that you currently installed in this iPhone is from a carrier that is not supported under the activation policy that is currently assigned by the activation server. This is not a hardware issue with the iPhone. Please insert another SIM card from a supported carrier or request that this iPhone be unlocked by your carrier. Please contact Apple for more information." We have contacted VerizonWireless in the USA through a friend and they affirm the device has been unlocked. But the message still appears, even after restoring the phone through iTunes several times. Any help would be appreciated!