iCloud storage full: "Not Enough Storage". Backups exceed 5GB
What to do when you do not have enough storage because your backup size is too large:


Delete the current backup on your iCloud for that specific iOS device.
Your iCloud backup is now automatically turned off, so turn it back on.
A new backup is made and has a reasonable size.


Theoretically your phone could crash in the short while you do not have a backup, so you could run an iTunes backup first.