iCloud storage full, but isn't full?

there are other data stored in the cloud such as contacts, notes, photo stream photos, etc. that you cannot see the storage for. You can contact apple support and they can tell you whats taking up how much storage in iCloud.

I was able to fix a problem with similar symptoms but a different cause.

I purchased a new iPhone 6s and sold my old iPhone 5s to my brother. I wiped my old 5s out and restored my 6s from a 5s iTunes backup I had. When I went to do my first iCloud backup on my new 6s it said my iCloud storage was full and showed about 3.5GB of "mystery" data. So I went in deleted some data off of my drive and turned off some backup items. This was just enough to fit a 2GB backup on. However, it said I had 126MB available which didn’t seem right since my backup was only 2GB. The ONLY other data showing up on my iCloud was 5MB in mail. I’m pretty sure 2GB + 5MB does not equal 5GB. I couldn't figure out what this other 3GB was.

I called apple technical support on two occasions. The first time they said backups are locked for a few days after they are first created and that I would only have to wait a few days. This didn’t work. The second guy said he could see two other backups from my old iPhone 5s on his end which I was not able to see on my end (iCloud on my phone or Mac). He said this was a know issue that will be fixed with the next iOS 9 update.

I had a different theory and didn’t like the answer I got so I called my brother and told him do the following:

1. Sign out of iCloud on his phone (my old 5s).
2. Sign in with my apple ID.
3. Go to iCloud storage > Manage Storage (he could now see my old 5s backups).
4. Delete my old backups.
5. Sign back in with his apple ID.

This immediately freed up my storage and everything is working great now!