I just gained a 25k privilege on Travel, where I have a lot more than 25k rep. So I guess it's a new privilege. Cool! But I haven't gained it on Meta or The Workplace, where I also have over 25k. Why not? Do they not have it yet? When will they?
The comments are correct: I have it where I expect to have it, though I was (at first) only notified for one (randomly chosen?) site. Since then I have got another notification for Meta. I presume the Workplace notification will show up eventually. (At one point it had been five hours with no sign of it.)
The notification for a site appears immediately after you earn some rep on a site. I guess for existing privileges is there is already a "now that you have more rep, did you gain a priv" code, and when a new priv gets added, rather than spawning a giant check, the system just counts on that code eventually notifying you. As noted above this has nothing to do with whether you have the privilege or not, just when you get notified about it.