I wish I had good news, but Google's way of supporting "friending" on Google Play isn't super great. It's a bit complicated to get someone as a friend, and even after that, it often doesn't work.They haven't been supporting it well either which is extra frustrating because there isn't anything we can do to help it from our end.
As I understand it, you need to both be connected to Google Play, you need to both have Google+ accounts, and those accounts need to both be connected in the same Google+ Circle.
These are the instructions that I found, along with the link for the page that I found it from:
You can use your Google+ account to connect with your Circles.
First, connect your game to Google Play by tapping the button in the Settings menu. This will connect your current Google+ profile to the game. (I believe you've already done this bit, but I put it here just for clarity.)
Once the game is connected, Google+ friends who play your games will appear in your Friends list. Both players must have one another in their Circles to see each other in-game.