How old is the fluid? If it's old or if the filter hasn't been replaced in the last 30K miles or so, I'd start there. The oil is thicker when cold and it could just be a simple issue of old oil + clogged filter.

On the topic of "Mechanic in a bottle additives" getting a bad wrap, I'll throw my experience in: My SDL had a really sloppy/crappy transmission in it and the yellow-bottle Trans-X really helped it out. Wasn't perfect, but it went from nearly undriveable with slow/hung/flaring shifts to totally acceptable.

__________________
Current stable:
1995 E320 157K (Nancy)
1983 500SL 125K (SLoL)

Gone but not forgotten:
1986 300SDL (RIP)
1991 350SD
1991 560SEL
1990 560SEL
1986 500SEL Euro (Rusted to nothing at 47K!)

Gone and wanting to forget:
1985 524TD 167K (TotalDumpster™) [Definitely NOT a Benz]