Could also be a bad coolant temp sensor, as they're known to be bad out of the box, sometimes 2 or 3 in a row before you find a good one. Did you clear the CEL after replacing the parts?