I have a few people in my life that own 16GB iPhones and they are constantly running out of storage space. John Moltz was able to save 6-7GB of storage space on his wife’s iPhone and about 3GB on his own by performing a restore in iTunes and then restoring the most recent backup.
I’m not sure if I’ll suggest this to others — I’m always concerned that someone might make a mistake in the process and end up losing data. But, this is something I’d like to try on my and my girlfriend’s iPhone. It’s worth a shot and has to be better than continuing to delete music in order to make room for new photos and apps.