As ParanoidAndroid mentions "H" stands for HSDPA which is an enchanced version of 3G
As for your GPS location, are location services definitely on? Also, it sounds weird but google recommends having GPS on as well when using the maps app, as they use the locally available wifi access point data to help pinpoint location.
I use O2 and live in London and mine is fine... gets a lock pretty quickly, with wifi off as well...