Sounds dodgy, unlikely your account has been hacked, probably a clever attempt at spoofing to make you click on the link to find out where the email has gone, THEN your account will be hacked.
IJP will probably have a better idea though.
For security:
Login to Gmail > Scroll down to bottom right corner > Last Account Activity, Details > Check for unknown locations + click Sign out of all other sessions.
Back to Gmail > Account (link top right corner) > Manage Security > Change password.
Whilst you are there ^^^^ It is worth turning on 2-step verification. This way, even if you TOLD me your password, I wouldn't be able to login without having your mobile phone as well.
I can't believe banks do not use that security method yet for online banking.