If the handset is new but your account is old (e.g. if you upgraded from an older iPhone), sometimes the MAC address needs to be updated so that the hotspots know you're allowed to connect. Call O2 and they'll reset it for Openzone and The Cloud. Or, send an SMS to '2121' with 'wifi' as the message. That will also reset it.
Also, I've found that many hotspots that are listed as BT Openzone in the wifi menu are actually BT Fon hotspots, which you can connect to but won't get very far when you open Safari. There is no way of telling which is which until you actually connect. If it's a BT Fon hotspot, you will get a login page when you open Safari. Unless you subscribe, you won't have any valid login details to enter. Proper Openzone will just open an O2 page asking for your phone number (the first time you connect after reseting mac address, this is what should happen).
In my experience, connecting to The Cloud hotspots is much more trouble free and never required a MAC address reset, problem is that there don't seem to be as many of them around these days compared to Openzone.
Anyway, first thing to try is to get O2 to update your MAC address on their system, or send 'wifi' as an SMS to 2121. That worked for me when my old 3G was replaced under warranty, and also when I upgraded to an iPhone 4.
Also, I'm not sure all new accounts automatically get free hotspot access thrown in anymore, so you might want to check your tariff too.