Are you seeing it in Google Play (the app store) or in the Google music player? If just Google Play, then that means Google is showing it on the cloud. You have to download it or pull it from the original source that you first downloaded the song. I know Amazon will let you do multiple downloads from time to time, but not sure what Google's policy is on downloading to a 2nd device, even if it's a replacement device. I've lost many legally purchased to the very inhibitive music industry's anti-pirating techniques.