Why does iTunes think my SIM card is unsupported?
If the handset was unlocked using UltraSn0w, then you have completely removed it by updating the firmware to the latest version (Ultrasn0w only supports iOS 4.3.3). Worse yet, this has updated your baseband and that cannot be reverted even if you manage to downgrade the OS (unless you used Pwnage Tools or Sn0wbreeze as they can preserve the baseband during update). If this is indeed the case, you have now a locked phone to whatever carrier it was purchased under (AT&amp;T) and you will have to talk to that carrier for a "hard" unlock.

To my knowledge, a "true" unlocked iPhone has no geographic limitations. As long as the network supports GSM phones (read: SIM cards), then there should be no problem.