Your 4S was probably not online when the unlock code was sent out to all Verizon 4S phones, from Apple. What has worked with others and you need to do is hook the phone up to itunes on a PC or Mac and do an update. If it fails the first time (about 50% of the time), do it again and you get the updated unlock from Apple servers.
The iPhone must be activated by Apple servers with the SIM you want to use installed. If it is active with another carrier before the unlock, you must enter the correct Apple ID and password for that previous activation, whether you activate over WiFi (with later iOS versions) or using iTunes. After the first valid attempt, you may get a message like this: "This iPhone could not be activated because the activation information was not correct. Please try again later." Unplug the iPhone from iTunes and plug it back in, or just re-enter the previous Apple ID and password if you are using WiFi. iTunes will show a splash screen with an Apple logo that reads: "Congratulations, your iPhone has been unlocked." (bold type) Below that: "To set up and sync this iPhone, click Continue."