Most services, such as Facebook, will let you know via e-mail if someone has tried to access your account from an unrecognizable location or device, so it's important to know when the e-mail's real and when it's not. In this case, it wasn't a legitimate e-mail.
You'll know when there's a legitimate warning. When you login it'll show a large red banner at the top which when you click X on will ask you to use a new password. It happened to a BS account I had and hadn't signed in for 7 years... My attempt was from somewhere in the UK. Google must sense a login pattern and won't complete a session login even if the password is correct.