I've just done an iCloud backup, Reset, and Restore from the backup, on my 8gb 4s. I decided that action was necessary when free storage reached zero. Deleting some stuff helped, but Photo Library was stated as taking 1.9gb of storage, even after deletion from the phone via iTunes, replacing Photo Library with an empty folder, and syncing....in short, following the procedure as recommended by Apple. As others have noticed, that does not always remove Photo Library from the device....or at least if it does, the phone still thinks that it's there and indicates it as using storage. Restoring via iCloud cleared it, as well as other unwanted stuff, giving a staggering increase in free storage from a few hundred megabytes to 3.5gb.