Your reply got me curious, so I tried searching the USPTO TESS [1] to match your results for the EU and the UK. With what appears to me to be the correct query, "(mario)[COMB] AND (nintendo)[OW]" [2], I found 39 results total and of which one was for the word "Mario" on its own [3] but that trademark was dead "because the applicant failed to respond or filed a late response to an Office action". According to what [4] says and given the time frame (filing date: Sep. 30, 1982; date abandoned: Dec. 23, 1983) this seems to imply that the trademark "Mario" was never granted. However, there are 22 trademarks that contain the word "Mario" and at least one other word that are live.
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....