Well after reading that I'm amazed. I believed region lock was based on where you lived and used the phone. Like a person in Europe couldn't use an at&t phone overseas until it was used in the states. I was unaware a person in the U.S. had to do the same if they were using it in the U.S. but with a different carrier. My apologies.
You wouldn't happen to know anyone on at&t would you? Maybe a Samsung rep in bestbuy can help you with borrowing an at&t sim and making a call or 2 on your phone.
Also Samsung is telling me that "as you have unlocked the device from third party site , and this is not considered as official unlock for the device"
I might bring the phone to bestbuy and let them check it out.. since the phone is still under Warranty