http://en.wikipedia.org/wiki/Wikipedia:Notability
In one sentence:
"If a topic has received significant coverage in reliable sources that are independent of the subject, it is presumed to satisfy the inclusion criteria for a stand-alone article or stand-alone list."
Notability isn't really that much of a judgment call.
Also, it doesn't necessarily apply to the creation of new articles. Stub articles are usually not well sourced at all.
The real story of the article is that Wikipedia's interface really does suck. It really is hard to figure out issues like this. It's even hard to monitor pages you want to protect, or have some interest in.
So, while the Wikipedians involved in the deletion process do have some grounds for their actions, it's left to the wiki-insiders to defend Wikipedia. That sucks. Until the day comes when a non-Wikipedian can arrive on the site, figure out what happened in the deletion process in 30 seconds, and then pronounce whether it was good or bad in some informed manner, we won't have an encyclopedia that truly anyone can edit.