Yes, start with a flush and also check for radiator leaks. E36's supposedly (I am told) have a high incidence of radiator leaks - minor, usually. But a trans leak is a trans leak. Look for pinkish fluid underneath your car after it sits while you work or in your garage; if there is so much as a drop, get that radiator replaced/fixed or whatever.
My 318i did this for a little bit, and it was due to a trans leak. In automatic cars (or so I am told) there are two clutches, one for the lower gears and one for the higher gears; this is why between 2-3-4 there shuoldn't be as many problems than in N-1-2; as that's where most of the shifting is (from stops and what not). That poor shifting CAN be one of your clutches burning. A 318i auto tranny will cost you about $3000. Not worth the car. So either hope it is funky fluid, or if I were you and you drove stick, I'd see if there's a kit to convert it to manual. Manual is so much more fun anyway...
1998 BMW e36 M3 Sedan
Crap, I think I may be a yuppie...
2003 MINI Cooper