It may be true. Orange and T-Mobile (and therefore Virgin Mobile also, since it uses the network of T-Mobile) work only on 1800 MHz
O2 and Vodafone started their networks only on 900 MHz (and in the past, some phones could not be 'unlocked' to be used for Orange/T-Mobile as they didn't cover the correct frequency band).
With the higher frequency (1800 MHz) the wavelength of the radio waves is smaller and sometime lengths of wire will react differently (and attenuate the signal).
If you check sites like www.gsmarena.com for different phones, you will find that some are dual band, some tri-band (1900 MHz is used instead of 1800 MHz in USA) and some are quad band (2100 MHz is being used here for 3G phone traffic).
Since you have found problems with Orange, I expect the same sort of problem might affect T-Mob (+ VM) but you may find Vodafone (and therefore Asda) would work OK, alongside O2.
I don't follow the exact coverage stats but expect all the networks have somewhere above 95% coverage for population (but big gaps in mountainous areas in Wales and Scotland). O2/Voda might have some slight advantage in such areas, as the higher the frequency, the more likely there will be problems if there's no "line of sight" to the cell mast. For comparison TV signals are in the 500 to 800 MHz area and have wide coverage, and FM radio is in the under 150 MHz area and work well even in built-up areas (where mobile phones only work because they have placed a lot of cell masts in towns and cities).