Well I'm sorry to hear this. There is no such thing as a "factory unlocked" phone, as the factory doesn't unlock them. They are unlocked via iTunes after the official carrier releases information to Apple.
ALL phones sold in the US are carrier locked to AT&T and they DO NOT UNLOCK PHONES, for any reason whatsoever.
This support article will provide you with the list of official carriers and which ones offer unlocking services for phones.
OS 4 has not been released so who really knows what you have and what has been done to it. I suggest that you do what you can to sell the phone and purchase one sold either in your country or one of the officially unlocked countries. On a side note however, warranty service on the iPhone is locked to the country that it is sold in, so you would have to return to the country the phone came from for warranty service, and they will not ship the phones outside of their countries as well.
Hope it works out for you.