Try deleting your current iCloud backup for your device and creating a new one. Like anything iOS related, it gets bloated. So it is probably saying your backup is larger than your 12GB free space, so it cannot write a new one.
Settings -> iCloud -> Backup -> Turn Off.
iCloud -> Storage -> Manage Storage -> Device Backup -> Delete Backup.
iCloud -> Backup -> Turn On -> Backup Now.