Why is my iPhone 4S showing so much "Other" data in iOS 7?

When you say that you've installed from scratch do you mean you restored the device and set it up as a new device without restoring from a backup? If not, try that.

The "Other" category for iOS storage contains a number of things including email, caches, settings, and so on. For >10GB of data I would guess its email attachments or the like.

If you have tried to set up the phone as a new device in iTunes, try resetting the iPhone from the phone instead:

Settings → General → Reset → Erase All Content and Settings

Once the phone reboots go through the setup on the phone, and then check your usage in:

Settings → General → Usage

That will tell you how much storage is available. It should be a more palatable number then what you've been seeing.