Q: Is my Iphone 4 unlocked for every country when bought in a Apple store?

I believe this has to due with your carrier.  When i was in the states i bought a phone for my wife and then one year later she had to move to Korea. The telcos in Korea could not set up the iPhone because AT&T did not authorise her to do so (her phone was on contract). So we had to pay to break the contract with AT&T before that would happen and pay the balance of the phone subsidy.

Our friends who left Korea just had to pay the balance of the phone (spread out over 2 years) before they left and it works fine in the U.S.

You just have to pay full price.

If you did not pay the full price, it might be locked to a carrier, check here if the carrier offers unlocking.

iPhone: Wireless carrier support and features

The unlock process has to be started by the carrier.

iPhone: About unlocking

iPhone is available for purchase and activation through Apple, wireless carriers, and authorized resellers (not all options are available in all countries or locations). In most countries, the place of purchase will verify that you have an account with the carrier, and then give you instructions on how to activate your iPhone. Verification of carrier account is not required in countries in which unlocked iPhones are available for sale.

Apple Online Store sells unlocked iPhone in the following countries: Australia, Austria, Belgium (French, Dutch), Brazil, Canada (English, French), China, Czech Republic, Denmark, Finland, France, Germany, Hong Kong (English, Chinese), Hungary, Ireland, Italy, Luxembourg, Malaysia, Mexico, New Zealand, Netherlands, Norway, Poland, Portugal, Singapore, South Korea, Spain, Sweden, Switzerland (French, German), Taiwan, Thailand, Turkey,  United Arab Emirates, United Kingdom, and United States.

copied from:

iPhone: Wireless carrier support and features

If you paid full price- yes. I would call your carrier and make sure they unlocked it.  Then you are sound.