I had 2-step authentication on my account. I then one day decided to change my gmail password via the web interface from a PC. I expected to get a notification on my android phone that I need to enter the new password. This however did not happen and I still received push gmail on my phone! I changed the password again and still the phone had full access to my gmail account. In the end I removed 2-step authentication via a PC web browser, logged out all other sessions and removed authorised devices from my account and only after a reboot of the phone was I prompted to provide the new password. I feel 2-step verification may be a security risk if your phone gets stolen although I am no expert on this but I was very surprised by the fact that changing your gmail password does not log your android phone out of the account.
Perhaps someone else can shed some light here? I mean its not like you can send an sms to your stolen phone asking the thief to please reboot the thing for you.
My guess is that your Android phone was logged into your gmail via an authorized password (which is used for devices and applications that are not two-step verification compatible). In this case changing your gmail password has no effect as the phone is still authorized...