iCloud has space but iCloud Backup says that I don't have enough to complete a backup
This could easily be explained as the 120 MB of used data is likely for the data all the apps store in iCloud. Contacts, calendars, specific third party apps can have storage in iCloud. You can determine this by looking at the Manage Storage pane in settings app (see below).

The warning you describe comes up when the expected size of the next backup is greater than the available free space.

You can reduce the size of the expected backup on iOS (updated for iOS 12) as follows:


open the Settings app
tap your AppleID/iCloud avatar (first item, top of list)
tap iCloud
tap Manage Storage
tap Backups
tap the name of the device in question (it usually says this iPod touch, this iPhone or this iPad to help if you have many devices connected to iCloud)
look at Next Backup Size
toggle off any unwanted apps from the list below


If that is less than the available space, you may need to contact Apple support to have your account fixed on the server side. In most cases, you can toggle off the largest few items and then attempt a backup when the estimate is less than the available space.



Once the backup is complete, you can tune the backups or manage your space as needed on iCloud.