Expect anything using the new 3G services to have patchy coverage. The network just hasn't expanded sufficiently yet to give anything else.
As I've pointed out before, do remember that whoever you actually sign up with, the physical network you are using will be one of only a very limited number. Leaving aside the new 3G networks, for regular GSM900/1800 service until very recently there were just four networks in Britain: Vodafone, O2, Orange, and T-Mobile (UK). To these have been added Opal Telecom and TeleWare, both of which have only started in about the last year.
So if you get GSM service with anybody else, it will be using one of these networks. Vodafone and O2 (which was formerly BT's Cellnet) are the longest established and have both GSM900 and 1800 celltowers, which tends to provide better coverage in more rural areas (obviously with localized variations). The others are GSM1800 only.