Is the "New" sensor actually new? You could try resetting the ECU perhaps to see if this does any good as it may still have a fault logged.

Martin