It’s also strange to me since more then once when discussing startup naming I’ve quoted this earlier article Paul wrote where he makes nearly the opposite argument: http://aux.messymatters.com/pgnames.html
I think it's still relevant. That was before most of the TLD expansion so .com was just about the only option. I the gist of the article is that you have a lot of options in naming and many/most of them will be fine (as long as you get the .com).
I guess to me the main point of the new article seemed to be that the prestige and “signaling of strength” associated with the .com is what makes it important, while the older article argues having a traditionally prestigious name can actually be a negative, in signaling that maybe the founders “have more money then brains”. (I understand he's referring here to names that are obviously bought from squatters, but still the main point seems to be don't worry if a name fits into the traditional mold or seems 'prestigious' as long as its unique, memorable and ideally communicates something about your business. I'd also never expect a newer startup to be able to find "stripe.com" or "parse.com" without paying significantly for them today.)
I’d also say the proliferation of new TLD domains has made them more, not less acceptable for new companies, especially ones like .io and .ly that have come to be pretty closely associated with the startups in general. Like you say, in 2006 nearly everything still was .com so a non .com might have stood out more as a negative, and even then pg says he still had no problems with del.icio.us
Also the last section stood out for me as a contrast with the title of this one:
"Whatever name you choose, be careful. Names stick. You need a way to refer to things, and whatever you call something rapidly becomes its name."