@Moses,

Most iPhone 3GS are unlockable unless there were made quite recently. So, maybe your 3GS was unlockable from the beginning and the first  person you consulted didn't know what to do or was unwilling, while the second person was trying to take advantage of you.

@Evans,

All iPhone 4Ss are both CDMA and GSM. technically, there is no difference between a Verizon, AT&T or even the factory unlocked one. What Apple does it to lock for each carrier as they order, and only them can unlock. It is similar practice used by al contract phone vendors.

My advice is that if you want to get an iPhone 4S, get a factory unlocked one. Currently, you will not be able to unlock a 4S or even the later model 4.