I get iCloud showing as full when there is often space left. My problem is almost always linked to iCloud documents and is corrected when I turn iCloud documents off and back on again (on my mac).
The space taken is inaccurate. My photos alone are 3.5gb. The reason I upgraded was because when I tried to backup my photos it informed me that I didn't have enough iCloud space with the 5gb plan.