See Duncan's answer for the reasoning the original author used. The problem isn't so much the total number of keys, but the problem of exchanging them securely; that is, if you share a key with someone else, you need to ensure somehow that who that someone else is who you think they are, and that no one else knows what that key is. This is certainly doable (say, by meeting them in private), but is not trivial.
Now, the problem with the argument that a complete graph is needed is that it isn't, strictly speaking, correct. There are ways to reduce the total number of keys in a complete graph using trusted intermediaries.
Here's a simple case of how this can work: suppose Alice, Bob and 998 of their closest friends all want to communicate securely. Instead of each one exchanging 999 different secret keys with all their friends, what they can do is find a person they trust (Trent), and each one exchange a secret key with Trent. Trent, of course, needs to store all 1000 keys, along with who each key belongs to.
So, when Alice wants to have a secure communication with Bob, what she does is pick a random key, and sends an encrypted message to Trent that says "I'm Alice, please send the K to Bob". Trent decrypts the message with his key with Alice, checks that it's reasonable (e.g. that it says that it's from Alice and not someone else), and then encrypts the message with his key with Bob, and sends it to Bob. Bob decrypts the message, and now Alice and Bob share a key that they can use to communicate securely. No one else knows what that key is (other than Trent, but we trust Trent). Alice and Bob can use their shared key for traffic between them, and discard it when they're done.
So, this procedure reduced the number of times we need to exchange keys securely from 499,500 (for the simple complete graph) to 1,000 (each person exchanges a key securely with Trent). Another way of looking at it; if Carol then joins the group, in the complete graph, she'd need to exchange keys with 1,000 other people, in the Trent scenario, she'd need to do it only once (with Trent himself).
So, the obvious question is: if this works so well, why do we use asymmetric cryptography. Well, because asymmetric cryptography does have some advantages:
In the above procedure, Trent had to be involved with the start of every secure communication. With PKI, the trusted party (Certificate Authority or CA) needs to be involved with giving out certificates initially, but does not need to be involved with establishing secure communications between two parties.
In the above procedure, Trent had to have all the keys, and also be able to handle active communications. This means that Trent is a very attractive target to hackers; they'd have valuable keying information, and a large potential attack surface. With PKI, CAs can be much more isolated.
Trent had to be trusted; if he wanted to, he could listen into every communication. CAs are also trusted, but to a lesser extent; they can impersonate other people, and they can act as an active Man-in-the-Middle between two people establishing a communication, but they cannot passively eavesdrop.
With PKI, not everyone needs to be registered with the Trusted Third party, if no one really cares who they are. That is, if Alice wants to make sure she's talking to Bob, but Bob doesn't really care who's he talking with, Alice doesn't need a certificate. This is a more common scenario than you'd expect; when you give your credit card information to Amazon, you really care that you are, in fact, giving it to an Amazon server; Amazon doesn't really care which PC you're using.