The calculations are slightly different depending on whether it is the Julian or Gregorian calendar, and whether the date in question occurs between January 1st and February 28, or March 1st and later (we'll ignore February 29, I think).
Consider first the situation in the Julian calendar, where there is a leap year every $4$ years without fail.
Suppose you have January 1st on a Monday, in the year immediately after a leap year. When will January 1st again fall on a Monday in the year immediately after a leap year? The pattern is:
M, T, W, R, Sa, Su, M, T, R, F, Sa, Su, T, W, R, F, Su, M, T, W, F, Sa, Su, M, W, R, F, Sa,
and then repeats; that is, a 28 year cycle. So, ignoring the leap year rule for Gregorian calendar, you could check for a period of 84 years (three full cycles). The situation is similar if your birthday occurs March 1st or later, except that the leap year affects you in position 4 instead of 5; you would have:
M, T, W, F, Sa, Su, M, W, R, F, Sa, M, T, W, R, Sa, Su, M, T, R, F, Sa, Su, T, W, R, F, Su,
and the pattern repeats.
In our putative example, which began on a Monday, we got each day of the week exactly $4$ times; that is, they all occur equally likely. If you chop it off at 80 years, then you'd be one short on four days. Changing the day of the week, or the time of the most recent leap year, would not affect the outcome: it cycles every 28 years.
However, the Gregorian calendar has a slightly different rule for leap years: in the Gregorian calendar, a year is leap year if and only if it is a multiple of $4$ that is not a multiple of $100$, except for the multiples of $400$ (that's why $1900$ was not a leap year, $2000$ was, but $2100$ will not). For someone born before $2016$, assuming a period of $84$ years, this will not matter because we will have a cycle just as above, with leap years every four years. But if you extend the lifetime so that it includes the year $2100$, then you start running into trouble because you skip a leap year.
You can think of the Julian calendar as repeating the pattern of leap years every four years; the Gregorian calendar, on the other hand, has a cycle of 400 years for repeating leap years. Added: And as Ross pointed out, while the Julian calendar has a cycle of 28 years, the Gregorian calendar has a cycle of 400. So you want to check what happens over a period of 400 years.
Over a cycle of 400 years, the number of times a given date (other than February 29) falls on a particular day does change (it's not uniform, like in the Julian calendar). If you start counting on a Monday, over the next 400 years, that date will fall on Monday, Wednesday, and Saturday 58 times each, Thursday and Friday 57 times each; and Tuesday and Sunday 56 times each. It's a pretty small difference over a period of 400 years, but there you go.