Unfortunately, the competition between carriers has become something of a three-ring circus as they all try to outdo each other. You know the deal: One company offers 240 free minutes, so another offers discounted calls on weekends, then the first retaliates by offering free calls to Outer Mongolia every other Thursday if there's an "R" in the month, and so on.
To pick up on a point from further up the thread:
They even have quad-band phones although I'm not sure where the 4th frequency band is required!
The four bands are 850, 900, 1800, and 1900 MHz. The 900 and 1800 bands are the ones used in the U.K. and Europe. 850 and 1900 are used in North America, although the 850 band is a relative newcomer for GSM service.
I'm writing some posts on telephones for the Technical Issues thread at the moment, so I'll try to cover the GSM band issue in more detail there.