The solution:

You have to create a completely new Windows Live ID (get.live.com or home.live.com). The e-mail address can be a custom one, don't bother creating a new @live or @hotmail address.

It's important to use Firefox during the registration process (IE detects your region).

Be sure to select:

1. Country/region: United States
2. State: New York
3. ZIP code: New York City ZIP code (search for one using Google)
4. Create a new Xbox Gamertag using your new Live ID (http://www.xbox.com/en-US/live/)

You can now login within the game with your new Live ID. That's it! Worked perfectly for me, and I did not change any other setting in my PC.