The problem could be that you don't have enough storage on the device itself, not on iCloud. Go to Settings>General>Usage to see how much "Storage" you have available. Farther down the list is the available storage on iCloud.
Go to Settings>iCloud>Storage & Backups>Manage Storage; there, tap the device you need info on and the resulting screen lists Backup Options with which apps store data on iCloud.
A device needs many MB of storage in order to perform a backup to iCloud.
Also see: http://support.apple.com/kb/ht4847