Are you sure you actually did a backup to the Google cloud storage? Keep in mind that it takes time to copy things, if you just installed Google Photos then shut off the phone and changed it, your files are not actually copied anywhere. Need details about your devices and exactly how you backed up the files to Google storage. Did you see them there before you changed phones? Did you logon to your Google account on a computer to check if they are there?