I think I may have discovered the answer. After mulling over the problem for a bit, I realized that not all cycles are created equally. The 19-year cycle just determines which years are leap years; it's the 247-year cycle which determines the lengths of Cheshvan and Kislev.
To test out my theory, I built an Excel spreadsheet, then went, column by column, down the Tur chart cited in my OP, recording just the number of days in each year.
The Tur codifies years by three criteria:
- The starting date of the year: ב for Monday, ג for Tuesday, ה for Thursday, and ז for Shabbos
- The lengths of Cheshvan and Kislev: ח if they're both 29, כ if one is 29 and the other 30, and ש if they're both 30
- Whether Adar II exists: פ for non-leap years and מ for leap years
As I don't care about the day of the week, I only looked at the latter two criteria, and listed each year by its length (353, 354, 355, 383, 384, or 385).
This led to the following spreadsheet:
Yes, it was more intuitive to me as well to do it left-to-right. But I was copying off of the Tur's right-to-left chart, and I didn't feel like switching the columns around after.
The top row labels which of the 13 cycles (247/19=13) that column is. The next 19 rows are the lengths of those respective years, with the orange rows being leap years (3, 6, 8, 11, 14, 17, 19).
The final row is what this spreadsheet leads to: the total sum of days in a 19-year cycle.
The problem that leads to the phenomenon noted in the OP is that although most cycles are 6940 days long, there are a few 6939-day cycles (and cycle 6 confuses things with 6941 days).
Well, you may ask, if years aren't the same length, then why should it be limited to Jewish leap years? Well, there's two calendars we're dealing with here, so let's figure out how long the corresponding Gregorian years are.
According to the Tur's chart, 5549/1788-89 was the start of the current 247-year cycle, so I decided to use that one. (Besides, if an urban legend is circulating now, it probably surfaced from recent data.) I didn't feel like doing the math myself, so I took the Gregorian dates for RH of year 1 and 29 Elul of year 19 and outsourced the calculations.
Rosh HaShanah 5549 was October 2, 1788. 29 Elul 5567, the last day of the first 19-year cycle, was, uh, October 2, 1807. That's... 6938 days. One less than the corresponding Hebrew cycle. So the 19th birthday of anyone born in that first cycle would have been one off.
Going through these calculations (read: making my computer go through these calculations) for these cycles yielded the following differences between the Gregorian cycle and the Hebrew cycle:
At this point I realized that I just needed to compare the Rosh HaShanah dates, and I didn't need to go through the second website and then compare it to my spreadsheet. But that led to another realization: this just compares the first year of each cycle with each other. It doesn't address the rest of the cycle.
But it did lead to an answer to the original question. It has nothing to do with being born specifically in a leap year that results in the 19 year cycle being off by a day. It's that the Gregorian leap year cycle doesn't follow the Hebrew 19 year cycle, which means that sometimes the 19-year cycles line up, while sometimes they don't.
It doesn't matter whether you're born in a leap year. It matters whether those 19 Gregorian years are the same length as the 19 Hebrew years.
I will have to look into the math at another time if Jewish leap years just happen to be more susceptible to being out of sync with the Gregorian calendar, and that's what led to the rumor I mentioned in the OP. However, this does explain the underlying phenomenon.