I believe during the Clinton era, but their support wasn't truly locked in until 2004. Clinton left a positive mark on young voters during his second term, but demographic and other changes really began to tilt that bloc towards Democrats in the mid-2000s. Now the weight of racial minorities and a substantially less Republican-leaning generation of white voters have created an age group largely hostile to Republicans.
I wonder: Had Gore won in 2000, would Republicans do better with young voters today?