I had a phone call with Apple Support yesterday, which was very helpful. I think there is a usability issue here - your local photos are using the same icon that your iCloud photos are using - to me that makes it confusing. I also think it's not clear from the screen that the storage info it's giving you are from two different places. It was so confusing, in fact, that the tech support person put me on hold for quite awhile to go talk to someone to figure this out.
So here I am, explaining what I think I learned in case it's helpful for someone else. Or in case I got it wrong, so someone can straighten me out.
I'm attaching a screenshot of my iCloud storage management here.
See how #1 and #2 aren't the same? I thought there was some MacMath going on here, where Mac was having trouble correctly calculating my iCloud storage. Why was it telling me it was full, when I clearly had 3 GB left.
Instead...
#1 on the screenshot (in 2 places) is the calculation of my storage space on iCloud. This is NOT the storage on my computer.
#2 on the screenshot is a calculation of the Photos storage on my COMPUTER, not on iCloud.
The reason I was getting the storage full message is because every time there was a new photo on my computer, or a screenshot, or I tried to login, or it tried to sync on its own, it would see that it wasn't possible to upload the part of the 21GB of photos that wasn't yet synced, into the remaining space I had on the iCloud. It wasn't just trying to upload that new photo. It was trying to go back and sync all 21GB of photos that I have on my local Mac in the photos directory, up to the cloud.
But I have a new install of Yosemite on a new hard drive, so how did I suddenly get 21GB of photos on it? Here's what happened. First, when I originally set it up, and connected it to iCloud, I said yes to letting it synced everything. Second, at that time, iCloud storage was over my storage limit. It was using 21GB of storage, even though I'd only purchased 20GB. That's because, at one time, it was allowing overages on Shared Photo Albums. I had a bunch of those. So when it synced, it downloaded 21GB of data, but then somewhere along the line, Apple's corrected this issue. So it came down, but then when it tried to go back up, the door was closed, and I got the error.
So I went in and cleaned out a bunch of the shared photo album data, which is what got me down to the 16GB on the cloud. But because there wasn't enough room for syncing ALL of the photos back up there, it was still popping up that error. It's also doing it on my iPad and my iPhone. The storage number showing now on my iCloud storage (the 16GB) is a combination of all of those photos from all of those devices uploading what they could to the cloud.
Priority One: Make that Message STOP!
The temporary solution was to go to the Options button next to Photos in iCloud Storage on my Mac, and uncheck the first two boxes. The first one makes my computer use the Cloud Photo Library as my primary photo library, instead of my local hard drive. The second one makes any new photos fire off that darn sync process, which was making the error box pop up. (The error box is a pain, too, cuz you have to DO something about it. You can't just close it.)
I also have to do this same thing with my iPad and my iPhone, if I don't want those photos to keep trying to go up there.
The permanent solution for me is to move whatever photos I have sitting on my computer, in Photos, that I DON'T want synced to the cloud, to an external hard drive instead. Same thing with my iPad and iPhone. Clean up the mess. Put it somewhere else. Only put in the cloud what I WANT in the cloud.
In my case, I don't want any new photos automatically uploaded to the cloud, and I don't want iCloud to be my only storage space for photos, so I'm not going to recheck the boxes I unchecked.
One last thing. To directly see and manage what photos are in your cloud storage, go to iCloud.com in a browser, login, and click on Photos. You can download any of the photos, move them elsewhere, and delete them off the cloud directly to clean it all up. This is SEPARATE from cleaning off your computer, your iPhone and your iPad.
Hopefully what I'm writing here is an accurate understanding of what I learned yesterday. If it's not, I hope someone will take the time, like I just did, to tell me (and anyone else who reads this) what IS correct.