I recently had my iPhone notify me that a backup could not be completed because iCloud was full, and have seen that happen on other peoples’ phones too. This can be annoying and confusing, but is easy to fix. Here’s a couple of links that might help if you run into this message.

Click here for a quick (yet slightly outdated) overview on how to manage your iCloud storage settings, or here for a more detailed explanation straight from Apple.