Initial troubleshooting steps
If you have an Android Mobile running Hangout App, just check if you are visible there!, if yes try going invisible or logging out of the app and check if still the warning message is displayed on Gmail.
To get rid of this issue, go to your gmail, scroll down to the bottom, you will see Last account activity and below it details, click on details, you will now have a pop-up window.
Click Sign out of all sessions and your done!
On the above window you can see all the recent sessions and locations where your mail-box was accessed. If you find a access location suspicious well, Alarm : Its time to change your password!!.