That's an interesting question. I did some very rough calculations assuming a constant rate of recession of 1.5 inches/year.
For the moon to move about 1/2 of it's current average distance further from the Earth (about 120,000 miles further out, enough to have a significant, but not catastrophic effect) would take just over 5 billion years. By that time a receeding moon will be the least of our worries, as we are heading for a merger with the Andromeda Galaxy in about 3 billion years, and our sun will run out of fuel and swell to a red giant phase -- toasting us, and the moon -- in about 4 billion years.
Hopefully someone else will weigh in if my numbers are off too badly.