iOS Update causes iCloud Photo Library issues
So I talked to the Apple Support and their solution was to...wait. So I waited until everything was uploaded again. This took around 12h. Then it started downloading files again, then it switched to "Updating" and then everything was fine again.

The person on the hotline said that it has to "upload" (It actually just checks if it's already on the server, not actually uploads the file) the file. Then it downloads what's missing and fills up the missing ones.