I'm pretty sure, unless I'm unable to show now, that I earn the "Vote Down" privileges before reaching 125 of reputation.
Indeed, obtained it at almost 110. I was really proud of myself ( ;) ), seeing notification, and I immediatly went to privileges list. I discovered that I was near 91%, or 93% or reaching the right level.
Is it a bug ? Is it possible to reproduce it (even now I got it) ? I didn't tried it, so maybe it is linked to Why did I receive a message saying I have been granted a privilege, yet I don't have enough reputation?, but I'm unable to verify it now.
If it's really linked, feel free to delete it (or let me do it by myself).