Is the Play Music app on the new phone set to Downloaded Only? If so turn that off and let it refresh and the song should show in your My Library area.
Welcome to Android Central! I agree with Scott337. The music should become available immediately in the Play Music app. Where are you looking in the app?