Make sure that both games share the same User id: gamename0000000.0000-0000000000000. If they don't, they're different games.
You could check the user ID on the loading screen (upper-left corner), or on the in-game settings' dialog window.
At this point, even if you couldn’t manage to find the first game ID, you should disconnect from Google Play your new game, reinstall it and connect it as soon as possible to the very same account you have had before.
If you haven’t linked your game with Google Play, your account can’t be restored.
Unfortunately, we can't check if your game was properly linked once you have lost your progress. That is why we recommend you check it regularly in the settings section. Take in mind that every reinstallation has a possible risk of losing your progress. Try to minimize these actions.
Please notice that your saved game will only be transferred to devices with the same OS.