Try this once and make sure you are not getting any error in project Structure saying that "ComGoogleAndroidGmsPlay not added"
Open File > Project Structure
and check for below all. If error is shown click on Red bulb marked and click on "Add to dependency".
This is a bug in Android Studio and fixed for the next release(0.4.3)