Sounds like an electronic issue - Fuses (C8 - Rht, C10 - Lft), a relay (there are 4 Hi/Lo speeds, Lft, Rht - #19, 20, 21 & 22), or the Series Ballast Resistor(s) PN# 996.616.101.00.
The easiest is to check the fuses and relays, though I'm betting on the resistor. If you still haven't removed and cleaned the radiators, here's your chance. The resistor is located in the wiring narness to the fans and you just splice a new one in. The fans will work w/ AC on because that is a high speed operation.
The one thing you need to do is get in there and see what's going on. It's possible that some debris has damamged the wiring or resistor, and they are a known weak point, such as the thermo-switch was on older brit cars.
Charles is right that the fans are moot once the car is going 35mph. At this speed, more air is forced through the radiator vanes than the fans can draw through. In fact, the fan blades actually become restrictive reducing the flow that would otherwise take place, though there remains enough to do the job.
If all else fails, the final component is the DME because this is what actually activates the fans. This failure does not throw a CEL but would be seen with a PIWIS or PST2 tester.
