Remove the drive shaft and pry the seal out. The typical replacement seal is short (no big rubber boot sticking out) but you should be able to get the original style.
However, if the tranny shop didn't replace the bushing in the tail shaft when they rebuilt it the new seal will likely start to leak too. The drive shaft yoke slips into the bushing.