Most of the time that argument is a convenient cop-out. You'd have to abandon your trademark pretty hard to lose the rights to it; leaving a few obscure online projects unmolested won't matter.
The real deal is that companies are very protective of their IP because they don't want anything to potentially impact their brand(s), and lawyers are eager to bill for as many hours as they can. It's possible that IP owners could commit a small team of goodwill ambassadors to filter alleged infringements and send licenses instead of (or quick on the heels of) C&Ds to good projects, but who's going to do that?
"Mario" is a current EU trademark held by Nintendo for categories 9, 28, 38 and 41.
- http://esearch.oami.europa.eu/copla/trademark/data/007061501 ;
- [UK:] http://www.ipo.gov.uk/tmcase/Results/1/UK00001182493.
The USPTO TESS db shows "Mario" is a character mark held by "Mario Camacho Foods, LLC".
It may be that the protection afforded is far less as people generally in TM law have an [near] absolute right to trade under their given name.
Why did Nintendo let the application for "Mario" lapse? I can think of least three options: 1) it was by chance; 2) their lawyers decided the trademark won't be granted; 3) they thought it was somehow undesirable to own the trademark for the word "Mario"; I wonder what it really was.
Anyway, you're right. The GP was mistaken that you cannot trademark common names [5]. Looks like he was right that "Mario" isn't a trademark of Nintendo's but for the wrong reason.
[1] Trademark Electronic Search System, http://tmsearch.uspto.gov.
[2] You can paste it into their "Free Form" search form. Unfortunately, it looks like you cannot link to search results directly.
[3] http://tsdr.uspto.gov/#caseNumber=73397991&caseType=SERIAL_N...
[4] http://www.uspto.gov/trademarks/basics/abandon.jsp
[5] For US examples see, e.g., http://tsdr.uspto.gov/#caseNumber=74259941&caseType=SERIAL_N... and http://tsdr.uspto.gov/#caseNumber=85026053&caseType=SERIAL_N....
Edit: Concern about trademark issues is also what apparently led to the Super Mario Clone FOSS project (http://sourceforge.net/projects/smclone/, note the URL) being renamed Secret Maryo Chronicles. I'm not sure if Nintendo ever contacted them or if it was a precautionary change.
Edit 2: There's some interesting commentary from a professional lawyer on the issue of trademarking and copyrighting characters at http://www.ivanhoffman.com/characters.html, though it's from 2003.