CheckGmail fails with "Error: Incorrect username or password"

New fix

Update: this started happening again on 08 Sept 2011 for different reasons.

First update checkgmail to the latest version (not the one included with Ubuntu):

Then download this helpful patch file (3 line change) and apply it:

Source: https://bbs.archlinux.org/viewtopic.php?pid=993642#p993642

Older fix

For all the gory details, visit Updating CheckGmail to Fix Login Errors.

For the lazy, just do this:

Voila, fixed.