A potential problem with cleaning the terminals' ends in the joining connector housings is that corrosion may have made its way to the terminal/wre conenction itself. The only way to be sure is to meter the wire capacity (ohms) from the terminals to the opposite end (the ECM behind the glovebox).
Having said that, I would reseve that check for the last resort. You can get to both ends by removing the console and working across the top of the transmission, through the floor penetration, but it'll take work.
Before doing that, if you're sure the NSS and conenctor housings are sound, I'd look at the transmission harnesses themselves. One feeds the NSS and though it the solenoids and the other is primarily the transfer case sensor pigtail. The problem is that Toyota mixed the wires in both sub–harnesses and they cross again at their connections to the ECM. It's not impossible to do, but I mention this because you have to check both sub–harnesses, not just the one connected directly to the NSS.
You also really need to have a verified EWD in hand while you work. And, to make matters worse, there are undocumented wire (color) changes in the harnesses.