Did you just get a new phone? If you did this might be it... When I went from the 4s to the 5 iCloud kept my old 4s backup after I restored and then also had my 5 backup for some reason. I just went in to where it says manage storage in iCloud settings on the phone and deleted the old one and it freed up what extra space it was using. Hope this helps
I have had this happen on 2 of the 5 iPhones i currently own. I have tried every tactic recommended by folks on forums & websites. The only solution that worked for me was to restore the phone and start over. Very annoying.
Delete your text messages. All photos/videos sent and received at stored and labeled as "other" and that is more then likely your cause. It's what happened to me and clearing my texts out weekly solved the problem.
I wish I'd thought to come here before I bought more iCloud storage in a fit of frustration after I couldn't get rid of the "not enough room to back up" messages. Even after deleting my old backup and removing *everything* from my phone's backup set my backup size was still 8g! Deleting all my old texts -lots of photos and videos I'd forgotten about - did the trick. Backup size is now back to a manageable 2.3 gigs. Thanks for the tip.
I had the same problem and had success by going into my iCloud system prefs on my mac, deleting all old backups from there as well as on my phone. I then restarted the backup process. My 4.5Gb backup shrunk to a reasonable 1.2Gb and now the math actually adds up.