This is a known issue with the S3. Even if you don’t put any apps, photos, or music on it, it will not have enough space for updates. For some reason there’s something that slowly eats up the storage and it isn’t reported in the usage report. I finally got tired of that nonsense and upgraded to the S6.