I faced the same issue today and after a lot of digging, discovered the cause and a solution.
Not only did my phone get stuck in the "Backing up 1 of xxxxx" state, but Google Play Services was consuming an excessive amount of CPU, and draining the battery even with the phone on a USB trickle charge. Going to the Google App settings and stopping backups would solve the CPU issue, but I was still stumped at the backup issue, after having uninstalled and reinstalled Google Photos to no avail.
What mystified me too was the very large number (xxxxx in "Backing up 1 of xxxxx" was over 11,000), because my phone at this point had only approximately 1000 photos.
Then it struck me, that perhaps Google Play Services was confused because I had externally removed thousands of photos from my phone via USB connection and Windows. So, after reassuring myself that this would not cause a major problem, I went to the Application configuration for Google Play Services, selected "Manage Storage" then selected "Clear all Data." I then re-installed Google Photos, and reconfigured, and voilà, the "Backing up 1 of xxxxx" message appeared, the count rose to the ACTUAL number of photos on my phone, and the first number then began ticking upward! About a minute after the backup completed, the CPU usage of Google Play Services dropped to normal...AND...the cloud icon with the slash which had appeared on all photos under Google Photos on the phone was gone! Not only that, but Google was smart enough not to duplicate these photos in the cloud itself as they had already been backed up via the prior version of Google Photos.
So, the bottom line is, when your phone is stuck on "Backing up 1 of xxxxx," it is very likely because Google Play Services is confused about the actual number of photos on the device...and the solution is to clear its database.