Does Google's multi-factor authentication make your security weaker?

A few months back Google introduced "2-step verification" for all Google accounts.  This amounted to multi-factor authentication (something you know (password) and something you have (token)) for all web-based Google applications.  Cool, right?  They created an app for the Android, I-Phone, and Blackberry devices that acted like a token and if you don't have one of these devices Google can just send you a code via a text message for you to use to login.  Okay so far?

Up until this point I'd say that Google has done a pretty good job on this implementation.  Of course we haven't included those users that access their Google accounts via a third-party program (Thunderbird for email, their Android device, maybe some plug-in for Blogger, etc). These programs don't have a mechanism for logging in with multi-factor authentication.  Google thought about this and created application passwords that you can use for a program to gain access without using a token. The passwords appear to be sixteen randomly generated numbers and letters and cannot be viewed after they have been viewed that first time.

This is an interesting concept.  Essentially you have many keys that now fit the same lock.  Loose control of one of those keys and you can simply nullify the key remotely.  So far so good?  Well, what you have also done is increase the number of keys that can get access to your system.  If a brute force attack were done against a Google account before 2-step verification was enacted the security was up to the user's password strength.  Now an attacker has multiple chances to gain access to the same lock because there are many more keys available.

I would like to point out that sixteen-character passwords are a lot better than most people's passwords which average eight characters or less.  But is having more keys to the lock (and knowing characteristics about that key) more of a security problem that what is being used without the 2-step verification?  I guess time will tell.  I would like to point out that I don't have a better solution to the third-party application issue. Perhaps some sort of machine readable token?