I'm also a fan of the utility Notify and find it a great way for me to keep an eye on what's happening over on Gmail even when I'm not logged in and don't have a browser running. I have also set up the darn useful 2-step verification process for my Google account (see Increasing Gmail security by enabling 2-step verification).

Problem is, third party utilities like Notify want to use the same password time and again with Gmail but don't have the internal pieces necessary to have 2-step verification work so when they try to validate their credentials and log in on your behalf, Google rejects it.

All hope is not lost. These sort of apps -- along with things like Google Voice -- are why there's a capability in Google that lets you set up different passwords for different utilities. A tiny pain, but that way you can also shut off access for a particular utility or application without affecting the functionality of the others.

Here's the error that I bet you saw in Notify when you tried to have it do a first check on your Gmail account:

You can Double Check all you want, but you're not going to proceed, even if you are 100% sure you've entered the correct password. Thing is, if the app isn't 2-step enabled, that password is no longer accepted by the Gmail system.

Instead, log in to your Gmail account and click on your name on the top right. When I click on my name, here's the menu I see:

As I've highlighted, you want to select "Account settings" to get to where you can set up one of those application specific passwords.

Now you'll see a lot of options, none of which seem to be exactly what we seek:

Turns out you want the selection "Authorizing applications & sites". Click on "Edit" and you'll be in the right section:

As you can see here, I've set up application-specific passwords for Google Voice and Google Cloud Print. Even within Google, some apps are 2-step friendly, others are not. "Notify" will be the first third-party app I enable too.

To set up a new application-specific password, I'll enter the name of the app (a good mnemonic device for later tracking) and click on "Generate password":

A click on the button and Google will show me the new password. App-specific passwords are four four-letter sequences separated by spaces:

What's interesting is that there is no way to ever have the system display that password again. This means you really need to copy and paste it into the app immediately (printing it would be counterproductive from a security perspective, of course). Got it all set up and copied into the application preferences / setup? Then click "Done".

Now, back at "Notify", something very helpful appears:

The green dot next to my email address shows that Notify is now properly communicating with the Gmail server using my application-specific password.

Problem solved!