Yep, I had the same problem after an iTunes restore on an iPhone and a TimeMachine restore on a Mac. iCloud Photo library appears to take all these photos as new photos and started to upload them all. I didn't wait for it to finish so it could've magically fixed itself but I didn't want to find out.
I nuked my local Photos Library on my Mac and all photos on my iPhone and let it re-sync from scratch.
That's clearly not how it should work but all is OK now.