Is it obviously engine oil? Thick and it could be (manual) trans fluid. Reddish and it can be (auto) trans fluid. Also depending on how clean they left the back of the engine it might be residual oil that is still yet to drip off.
Other possibilities are the nicking of the seal already mentioned, varnished oil/debris still on the crank sealing surface - or was the seal even really changed? Not knowing the integrity of the garage some establishments might have poured a can of seal sweller in the crankcase (hoping for the best) and charged you for a replacement. Odd as it may sound the rubber seal can also wear a groove in the steel/cast metal crank and affect the ability to seal. This though is more common on the front where belt accessories cause loads.
The seal replacement requires removing the driveshaft, linkage, starter, crossmember, trans, flexplate/flywheel before the seal can be reached and is the classic 'hundreds of dollars to replace a $5-10 part.' Does the car show signs that these items have been removed?