I dont think its a big challenge technically. There’s no shortage of quad-band phones. Most of this is business driven. I think in the case of the NexusOne it was just rush to market or AT&T not wanting in on the deal. The FCC needs to certify all radios and it was probably quicker to just get certified for T-Mobile.
In the US its expected for someone to buy a phone for a small fee and pay more per month to make up for it. In many countries the opposite is true. You pay a hefty fee for the phone and pay less per month for service, as you are just buying service not a subsidy for your phone. So why should US companies make these phones portable? Yes, it would be nice, but the US system lends itself to lock-in.
T-mobile recently is allowing European-like pricing. Buy a phone and get a cut on your monthly.
Nexus One isnt locked into T-mobile. It uses 2100mhz, which is the most common 3G UMTS frequency worldwide (I think). At launch google said its going to work in the UK, Singapore, and Hong Kong. Delaying the product just for AT&T doesnt make much sense, especially if AT&T’s relationshop with Apple means they might not even allow it. Google has announced a Vodaphone model for Europe and a CDMA model for Verizon in the US. I have a feeling that AT&T just told them to piss off.