Simon, if you must use an op-amp instead of a comparator, use something like this (attached). I bet the designer of the original circuit stuck the logic gate in there because the output offset voltage of the op-amp when 'off' was enough to turn on the transistor driving the relay at all times. Putting a low value zener in the base circuit gets around this without resorting to a schmitt trigger. The 4.7K resistor provides enough pulldown to overcome the leakage of the zener. It might need to be lower, 1K-2.2K.
The 1N914 diodes provide ESD protection for the op-amp if the temperature sensor is mounted remotely. Another pair of diodes will need to go on the set-point potentiometer if that is mounted remotely too.
This circuit will energise the coil when the temperature is lower than the set point. If you want the relay to work the other way, reverse the inverting and non-inverting inputs, but move the feedback resistor to the non-inverting input and exchange the 1uF and 100nF caps. The 100nF is a bit low for noise smoothing, but speeds up the hysteresis action. Try changing it to 1uF. Or, just swap the temp sensor and it's pullup for the same effect.
You'll need to select the unlabelled resistors for your application.
You might want to run everything to the left of the relay coil from a voltage regulator if the supply is noisy or if it's likely to go over 32V, even transiently. The op-amp doesn't like it up it.
The diode in reverse parallel with the relay coil is a 1N4007, transistor can be TIP122 if the relay is a big bastard, or BC337-40 or something if <50mA coil current. No zener in parallel needed.
Remember, if you do use a comparator, it will probably have an open collector output and a pullup on its output will be necessary.
In theory it's easy to do with bugger all parts, but in the real world where there's noise, ESD and crap, additional protection components are required. I've probably forgotten something, I'm sure someone will point out if so!