I am trying to find an average length of employment for a group of
employees at the time of their promotion. I am using the formula
below to calculate each employee's time in service at the date of
promotion:

=DATEDIF(D4,E4,"y") & " Yrs, " & DATEDIF(D4,E4,"ym") & " Months"

whe
D4 = beginning employment date
E4 = promotion date

What I would like to do is average the time on the job for the
employees promoted in each group. I cannot simply average the column
due (I think) to the text in the output.

One way is to base the calculation on the original data, rather than on the
concatenation; for example:
=INT((AVERAGE(E:E)-AVERAGE(D:D))/365.25) & " Yrs, " &
ROUND(12*MOD((AVERAGE(E:E)-AVERAGE(D:D))/365.25,1),0) & " Months"

Explanation: the average of a bunch of differences equals the difference of
the averages.

Modify to suit.

(I use Excel 2003.)