Photos not backed up to iCloud even though I have space
If your iPhone storage itself is full, it can stop the ability to upload to iCloud.

Are your other devices able to upload new photos?
Sign in-and-out of iCloud?
Reboot the phone?
Double check your wifi connection or enable uploading over cellular?

Source: MacWorld