Entertainingly enough, in the USA there's now a service called Straight Talk that lets you use a locked GSM phone as long as it's locked to an AT&T or T-Mobile network. We just picked up a barely used AT&T network Samsung Galaxy S II for $150 off craigslist (new they're $350 on the shelf with no contract) and then bought the $15 AT&T-compatible SIM and everything is working fine.
They offer SIMs for T-Mobile, AT&T, and unlocked GSM phones. The CDMA option at top is there to notify you that "This program is not available with CDMA (i.e. Verizon, Sprint, Metro PCS), TracFone, SafeLink, NET10, Straight Talk or BlackBerry phones.": http://www.straighttalk.com/shopsims