Very often when transmissions go lots of "crud" winds up in the fluid. A lot of this crud can get lodged in the cooler, in the lower part of the radiator. It's very hard to flush all the crud out of the cooler. Many shops, that don't want to see you again, will either replace the radiator or bypass the cooler and put in an external one.
You transmission may just be suffering from having the cooler partially blocked. You may be able to salvage it by getting the trans power flushed and having an external cooler put in (with the old one bypassed).
Rebuilts will never last as long as the original. You can get pretty good life out of them by: using synthetic ATF, getting it changed every 20K miles and using an external cooler.
