Other includes data such as iPhone settings, contacts, calendar events, Safari bookmarks/cache/cookies, email and email attachments, SMS/MMS/iMessages, notes, app data, Safari cache, cookies and bookmarks, stored passwords, search index, home screen organization, wi-fi network data, etc. Sometimes it can continue to grow over time to an unreasonable level. It should generally be about 1GB. Yours is much larger than it should be. This can usually be fixed by backing up your phone, the restoring it and restoring to the backup at the end. If this doesn't fix things, then the problem is contained in the backup and all you can do is either live with it, or save as much of your data as you can, then restore your phone as new (without using your backup) and start over.
When Other grows that large it can sometimes result in the problem you are experiencing. You can see if switching to backing up in iTunes, then back to iCloud will resolve the problem if you want, but your Other is likely to continue to grow until you address the problem by restoring your phone.