Hi Phil,
I don't think my fans come on straight away, even if the aircon is on, but, after a short while the fans do come on. The fans on mine come on far too soon for it o be engine temperature, so, I'm fairly sure it must be by monitoring the air conditioning refrigerant pressure.
It's entirely possible that your fan control system is OK, but that there's a fault elsewhere.
I wouldn't rush to throw parts at it without checking. The relay itself should be easy to check - typically you would connect a battery across the winding, and check the relay closes.
See
http://faculty.ccp.edu/faculty/dreed/AT121/at121files/relays.htm
for more.