I have the same truck and did a little write up as the result of trouble code P0125.
Here is my write up on Ultimate Yota, with some pictures and part number.
http://www.ultimateyota.com/showthread.php?9623-Trouble-Code-P0125
I got the code without the decrease in fuel mileage. I was about to leave on a trip, didn't want to travel with the code so I went to the dealer for the part. From what I've read and heard you want to go with a factory part as it will last longer.
My 5 speed transmission made the replacement of the sensor of PITA. I ended up having to go through the top of the transmission tunnel and I believe I had to break the clip that held part of the wire. I was quite sore from the wrestling I had to do while holding an inspection mirror, flashlight and seal pick.
TheDurk posted that the sensor will fall with the sensor, not on my truck. It will do that now because I broke the clip which makes me believe his has been changed before. The clip is held on with a bracket that is held in place with a bolt on top of the transmission. That was hard to access plus the plug for the sensor had a kung fu grip and would not release.
It's been some time but my mileage was only super good for less than 1000 miles. It's back to about where it was, as in it didn't make a huge difference.