The fan has nothing to do with cooling the engine at hiway speeds, they don't have enough air flow. Suspects are the radiator, water pump, or major engine problem such as cracked head, headgasket or cracked block.
Radiator - Did the shop rod it out? If so, did they have to block off any passages?
Water pump - Even if it's new, if it spins too fast, it can cavitate the water behind it, stopping the water flow. Cure is to put on a bigger pulley. Also inspect the impeller for damaged blades.
Cracks, leaks - Check coolant for bubbles or signs of oil. Also check oil for coolant. Inspect engine in the morning before it's started, looking for coolant around head.
