Did you publish the Game Services for the game? In the Google Play Cunsole, click on Game Services, then you should see the name of your game and under Status it should say Published.
Also, even if everything is set up correctly, I have noticed serious lag with requesting score, submitting score, and then after you've logged a new high score, showing the leaderboard.