Nostalgia can begin any time, I think. I've had times where I've been nostalgic for something that was only a year old.
I think a key factor is you have to have had a perception that something has changed. Weirdly I find my own nostalgia isn't always for things I felt good about. There's been a lot of things I disliked and thought were dumb during their day, but then I missed when they were gone.