Despite an erroneous help sheet on Apple's website right now, which claims that only EE and Vodafone's 4G would be compatible with the new iPhones, all four major UK networks have confirmed to us that they'll be carrying the new iPhones, and yes, 4G will work.
For now, it seems that Apple's not-so-helpful guide to which networks the iPhone 5S will work with is just plain wrong, as both O2 and Three have confirmed that they'll be carrying the new iPhones, and that they'll be compatible with their networks.
That agrees with the tech specs, where the international iPhone models are both shown as being compatible with the 800Mhz, 1800Mhz and 2600Mhz LTE spectrums -- the full range of spectrums used for 4G in the UK. We'll update when we have work (or a correction!) from Apple.