I would say that generally, the burden of proof falls on whomever is making a claim, regardless of the positive or negative nature of that claim. It's fairly easy to imagine how any positive claim could be rephrased so as to be a negative one, and it's difficult to imagine that this should reasonably remove the asserter's burden of proof.
Now, the problem lies in the fact that it's often thought to be extremely difficult, if not actually impossible, to prove a negative. It's easy to imagine (in theory) how one would go about proving a positive statement, but things become much more difficult when your task is to prove the absence of something.
But many philosophers and logicians actually disagree with the catchphrase "you can't prove a negative". Steven Hales argues that this is merely a principle of "folk logic", and that a fundamental law of logic, the law of non-contradiction, makes it relatively straightforward to prove a negative.
In practice, I think the truth lies somewhere in the middle. Hales seems to be making the argument that it's possible to assemble a formal logical proof of a negative statement. He doesn't guarantee the possibility of conclusively proving all of the premises of such argument. That is all well and good, but the average person rarely finds formal logic proofs very persuasive. The real problem is that negative claims often make assertions about things that we are in practice either unable to observe altogether, or that are difficult to observe in finite time.
Consider, for example, I make the claim that "there is no intelligent life on other planets". Certainly it seems intuitive that I possess the burden of proof for such a statement. But as discussed, it would be extremely difficult, if not impossible, for me to actually provide a compelling proof of this claim, because it's impossible to conclusively examine the entire contents of this and every other universe, looking for intelligent life (even putting aside such technical issues as what barometer we use to measure "intelligence", or even "life").
Certainly, following Hales's example, I could make the following "logical" argument:
Premise A: If intelligent life were to exist elsewhere in our, or any other, universe, we would be able to make contact with it.
Premise B: We have been unable to make contact with any intelligent life in our, or any other, universe.
Conclusion: Therefore, intelligent life does not exist in our, or any other, universe.
But I guarantee that anyone reading that argument is immediately going to object to the first premise. Some would probably even quibble over the second. In a strictly logical sense, my argument is sound: if the premises hold, then the conclusion follows. But that doesn't mean it will manage to convince very many people. The reality is that because negatively-phrased statements often make such sweeping claims, it's very easy to conceive of potential counter-examples or poke holes in the premises of those proofs.
But I don't think it's accurate to say that the burden of proof falls only on those who claim non-existence, either. Consider that I were to make the argument that Santa Claus exists. Why should the burden of proof be on you to disprove that argument? Certainly in making a claim, I should possess at least a minimal burden of proof to substantiate that claim, right?
So my general rule, and one widely followed in philosophical debates, is that the person who is making a claim always holds the initial burden of proof. Once that claim is made and the burden of proof is overcome, the burden of proof falls to any challengers of that argument, because what is a challenge to an argument but a claim to the contrary?
The way I see it, it's logically disingenuous to allow people to get away with making any type of argument without providing some sort of proof for that claim. For what it's worth, I've never heard the premise that you lead with in your question, and it strikes me as downright specious. A person who claims that "God exists" should have just as much burden of proving that assertion as a person who claims that "God does not exist". Why should I be free to spout nonsense just because I rephrase it as a negative?