So I understand that a restore will usually remedy this issue. But do I have to do a clean restore and start everything completely over or can I restore from a backup (or does the backup likely hold all of the extra "other" data)?
Unfortunately iOS has an annoying aspect where Documents and Data for apps is allowed to grow out of control with no way of addressing it other than to delete / reinstall apps (losing all of your app settings in the process).
For example the Yelp app is currently only 27.5 MB in size but quickly swells to ridiculous levels. Mine is currently 918 MB.
The balance is stored as Documents & Data.
You can check your worst offenders in;
Settings > General > Usage.
They did briefly allow you to delete it from the app usage screen in either an iOS 5 or 6 Beta which I would love to be able to do for some apps.
Worst offender for me is iTunes Match and Music. You can delete the "cache" in the Usage settings, but it will also delete any songs you've downloaded for offline play. Same result if you turn Match OFF then back ON.