Shop replaced 02 Xterra Auto trans hose. A "cleaner" needed to clean leaked fluid. Now Console shifts w/difficulty. Could this "cleaner" have cleaned the linkage as I understand it's normally greased?

Brown trans fluid... If you change the trans fluid now' odds are it will start slipping very soon. Couple hours to a day.. You will most likely need a transmission shop to flush and perform adjustments.
My experience, shop may offer 3 yr warranty at a price. You should be able to negotiate a lower price for say.. one year warranty. My opinion. If it good for a year, it's good to go. Those other things changed, all well and good, but not really related to trans. Does it still use a vacuum modulator? That's a low cost change.. (ck the vac hose) but if fluid is brown you won't have long to run.

I assume this is an automatic?
If the shift linkage is not damaged (jammed or disconnected the usual answer is the governer valve in the transmission is sticking.
The fix for this normally involves pulling the trans out stripping it apart cleaning the governer valve new seals gaskets and reassembling.
(translated lots of money) try using a auto trans flush to clean all the gunk out of the transmission. Run the trans through all the gears with the trans flush and try driving it (only short distance test drive as its not proper trans fluid) see if you can get it out of first gear (flatten the gas pedal and let the engine go to max revs on short bursts) once it shifts once or twice go back and remove the trans flush fluid and replace with correct specification auto trans fluid I would also change the transmission filter at this point if it was mine .

No vacuum hose as this is an electronic shift control trans. Check the fluid condition and rad cap to see if there is any cross contamination due to a faulty trans cooler in the rad. If MIL is on check code

The first thing you should have done is to have all the transmission fluid flushed, this may be due to worn out fluid friction modifiers causing torque converter clutch chatter.

indicates an actuator problem
check vacuum hose for a leak and check unit for adjustment

For Automatic transmission problem,click the link below:----Automatic transmission troubleshooting:---- http://howtobyme.blogspot.com/2011/11/automatic-transmission-will-not-go-into.html---------Automatic transmission shift lever issues?------- http://technoanswers.blogspot.com/2012/01/automatic-transmission-shift-lever-hard.html
-----------AUTOMATIC TRANSMISSION FLUID LEVEL? --

http://schematicsdiagram.blogspot.com/2011/07/how-to-check-automatic-transmission.html

--------------

AUTOMATIC TRANSMISSION FLUID AND FILTER?
http://schematicsdiagram.blogspot.com/2011/07/how-to-change-automatic-transmission.html
-----------Transmission fault light on car dash? http://schematicsdiagram.blogspot.com/2011/12/transmission-fault-light-on-car-dash.html
--------Transmission shifting problem? http://schematicsdiagram.blogspot.com/2012/01/transmission-shifting-problem-on-toyota.html
--------Transmission Slips out of 2nd gear?

http://repairhelpcenter.blogspot.in/2012/02/transmission-slips-out-of-2nd-gear.html

-----------
OD light flashing and transmission fluid leaking?

http://repairhelpcenter.blogspot.in/2012/02/od-light-flashing-and-transmission.html

----------
Why Transmission fluid leaks near radiator?

http://repairhelpcenter.blogspot.in/2012/02/transmission-fluid-leaks-near-radiator.html

----------
transmission fluid leaking?

http://technoanswers.blogspot.in/2012/02/ford-windstar-transmission-fluid.html

-------------
****** wont go in reverse?

http://technoanswers.blogspot.in/2012/02/dodge-neon-wont-go-in-reverse.html

-------------
Automatic transmission will not go into reverse? http://technoanswers.blogspot.in/2012/02/dodge-automatic-transmission-will-not.html
----------Transmission is making buzzing noise? http://technoanswers.blogspot.in/2012/02/transmission-is-making-buzzing-noise.html
-----------This will help.Thanks.

Several things to do about this. Look in your Radiator reservoir for a oily sheen and do the same thing for the Radiator if it has a cap and is not sealed. Have the Trans fluid changed and the Trans filter serviced. If possible get a sample of the Trans fluid.

If both the fluids look normal you only need fresh Trans fluid and the Trans filter serviced. Some filters are replaceable and some are just screens which need periodic cleaning. If the fluids do not look good then the Radiator may be leaking into the Trans fluid via the cooling lines. The delay may be due contamination corroding the first of many parts.

The gear engagement is dependent on engine RPM. If, for some reason your motor is idling slower at Startup, the initial gear engagement will be delayed. You could also be down on fluid, which would mean another problem.

The chances of cross contamination are very slim, but it is mentioned because your shifting can be affected in small ways at first, then big costly ways. The self-diagnostics in your car does not cover this problem.

Take the time to check the reputation of the shop you deal with for this simple service.

to change your tranny fluid and filter is relativily easy i will tell you step by step here.
1. raise the vehicle and support it with jack stands
2. get a large drain pan
3. locate the transmission oil pand and losen all the bolts removing the rear half of the bolts only and just losening the other bolts to keep the pan held up but allowing it to sag on the rear.
4 be carefull because in this step your likely to get a bath in tranny fluid. insert a flat srewdriver in the back of the pan and carefully pry it lose. now trany fluid is going to pour out of the pan.
5. remove the rest of the bolts be carefull because the trany pan still has a lot of fluid in it.
6. grab ahold of the filter and pull it down.
7. insert the new filter but make sure the rubber gasket came offf with the old filter they have a tendency to stick in the transmission.
8 replace oil pan and torque down evenly
9 refill with correct fluid to the correct level
10 take for a drive and recheck the fluid level and check for transmission fluid leaks
ps when the pan is off clean the inside of it out with brake cleaner really good
If there are no leaks after you get done congratulate your self on a job well done

hope this helps you
please rate me
Thank you

your owners manual will tell you exactly. usually all filters should be changed (oil, air, auto transmission if equipped, fuel, cabin air etc) as well as spark plugs and wires, distributor cap and rotor if equipped, check the belts and hoses as well as the charging system. All fluid levels should be checked and topped off. Check your tire p.s.i. as well.

Your transmission fluid contain water,thats why the colour of the fluid changed to pink.And of such the clutch is slipping causing the engine to reve up before shifting - Check transmission cooler.