They should have check the pulley and alternator when you took it in to get a replacement. You should have left with the exact same measurements you came in with. If the tensioner is at the end of it's travel then the pulley is too small. If the tensioner can tighten the belt more but doesn't hold it there the then tensioner may need replacement.
Next time when you get parts make sure you get the exact same part and if they aren't exactly identical make sure all the critical measurements are the same.