I don't know your engine specifically but if your connector is not fitting,
It is very likely you have the wrong part.  My 99 explorer has a coolant temp
sender for the computer and one for the temp guage. I believe there is
another for the A/C.

You should not have to change wiring to put in a new sensor.  Double check
with the dealer that you have the right part and have them print out a copy
of the parts diagram thay are looking at and show you where it is on the
engine - you  might be looking at the wrong one.

couple of questions for you.  
first:   was the engine up to temp when you had the code pulled? a cold
engine will generate the same code and there is nothing wrong the code can go
away when the engine reaches normal operating temp.
second:  common on the ford 5.4L.  they have a Baro sensor or barometric
sensor that reads air density. the sensor is part of the mass air sensor
located on the air filter box. you wont get a code for this and here is why.
this sensor tells the computer the density of the air for the proper fuel
mixture. if you live at sea level the air is more dense the up in the
mountains.  when the sensor goes bad it usually starts to read as though you
were up in the mountains. common problem for people who use k&n filters
because the oil from the filters contaminates the sensor. the only way to
test it is to get a scanner that can read the baro like a snap-on scanner it
should rear 159-160 Hz. if you are at sea level.  since the car doesn't
really know if your are in collorodo or Florida it has to rely on this sensor
so if you are in Fl. but your car thinks you are up in the mountains you will
use a lot more fuel and the engine will run a bit richer.

Back to your temp sensor. follow the upper rad hose to the intake the sensor
will be in the first passage of the intake probably on the passenger side of
the engine.
hope this helps.