Natural languages are not formal mathematical logic.
In formal logic, you’re absolutely right: “Everybody does not have a water buffalo” would mean that everybody is sadly buffalo-less; it would not be the same as the negation of the statement “everybody has a water buffalo”, which would be “not everbody has a water buffalo”, or “somebody does not have a water buffalo”.
However, with natural language, the litmus test of grammaticality is something like: if, within some speech community, a construction gets used, consistently, and understood, then it’s grammatically correct, within that community. And by that test, this usage is grammatically correct — I’ve come across it pretty widely, in speech and in writing, in the UK and US and Canada, in popular culture and academia.
…and for all that, it irks me a little too — this is a case where what’s idiomatic seems to clash particularly badly with what’s logical. As Robusto and chaos show, one can make arguments for how it is in fact logical, but I don’t think those are what this usage comes from; I strongly suspect it’s just that one normally negates a clause by negating its main verb, and so that pattern gets used here too, even though that also slips the negation past a quantifier, which (as any fule kno) is Not Kosher.
It’s this disparity between grammar and logic that makes much legal and technical prose a minefield — but on the other hand, the plasticity of language that gives rise to this is something extremely important and valuable in itself, which one would hardly want to give up. You can’t have your cake and eat it, I guess…