Eugene's observations

There be confusion in the shires as people receive "Password Incorrect" errors when the password has been held in the mail client (Windows Live Mail, Outlook, Thunderbird, 3rd party email apps on Android devices etc.) unchanged for years. This causes folks to think their account has been hacked so they change the password; but woa - the same error message pops up again ! What's that about ?

The security minded people who run Gmail unilaterally decided that the old way of authenticating: passing your username and password in unencrypted form, is too insecure for comfort. So rather than setting an appropriate error message they chose to frighten folks with a cryptic puzzler.

This only applies with mail clients using the older 'basic' authentication methods such as those above; clients using OAuth 2.0 will not suffer so. What's to be done ? There are three possible solutions.

1. Switch to a better secured mail client. Sounds simple enough but it's a right pain to get all old messages, contacts, and calendar entries moved. Never mind learning a new interface.
2. Switch on two factor authentication. This is a good balance between increased security and spending a lot of time reconfiguring. You will need a second device to authenticate with, but who doesn't have a smartphone these days. If you don't there are alternatives such as Google Authenticator and GAuth Authenticator. You may need to create an app specific password in the process for the app or service too.
3. Turn off Gmail's enforcement of the limitation by modifying your Google account to "allow less secure apps".