This kind of approach is, in the tradition of Wolfgang Pauli, "Not even wrong." Like the dog with Buddha-nature.
'Nothing' is not 'vacuum'. If I came up to you and brought nothing with me, few drastic results are likely. If I came up to you and brought vacuum with me, you would likely die, as all your cells decompressed. In that sense, emptiness is a physical force, and empty space is a real thing, not a 'nothing'.
At the same time the Parmenidean 'Nothing' as a supernatural construct also just seems to be a misunderstanding waiting to happen. One version of the Bogomil heresy goes "Deposed, Satan had nothing. He therefore rules the world. For nothing is more powerful than God." This may be deeply motivating to Satanists in a religious sense -- but it is not logic.
Negation is a verbal convention, not a Category, as Kant would have it be, or some other deep force of nature. To me, the fact that it has intrinsic problems like Russell's Paradox indicates that it is not a reality, just a human convention.
LeDoux's "The Emotional Brain" points out that we have one entire layer of memory processing that we share with lower animals which is, in a very basic sense, incapable of processing negation. It is a common theory that the gap in speed between this layer and our fully engaged frontal lobe leads to things like phobias, PTSD, and Tourette's syndrome. If negation were so basic a part of actual reality, we would not have evolved it so late that the system that implements it lags behind our more basic processing.
-- Sorry to add so much later. I always get to that point where I think I made the answer obvious only to later find I have not stated it --
As the last thing we property evolved mentally, I think negation is not quite right, not complete. Trying to push evolution, humans have a bit of an obsession with 'nothing' as a concept. But urgency is not importance, and our occasionally-urgent feeling that these 'deep' questions about 'nothing' matter is misguided.
If we look at this less obsessively, Krauss is free to work from a model that the world originates in vacuum, and it is obvious what he means by nothing is not what someone more careful means by nothing. But even that is silly. The oversimplification just makes him bound to an incomplete paradigm, one without a more basic notion of nothing, and not wrong.
(Ellis can judge this paradigm non-falsifiable, and thus not science. From a Kuhnian perspective, that only makes it non-normal science, not inadmissible as science, because 1) paradigms are not falsifiable by nature, only contrastable with comparable alternatives; and 2) I do think there are clear alternatives, and that it is productive to consider those scientifically as well as philosophically.
There are competing models, and I think those do have potential test cases. For instance, some predict very specific ways to send information backward in time (e.g. this crazy man http://phys.org/news63371210.html), which would break down the notion that extrapolating time backward linearly to some beginning has value, and make Krauss irrelevant -- but still not "even" wrong.)