iPhone storage doesn't add up?
Please check out What is other on iPhone Storage to get a nice way in finding your hidden storage waste.

Also to give you a nice way to fix this. Restore your iPhone to the most recent version and then place the backup file back. Don't just update as it won't remove anything.

Also check out this Apple KB about the space issue.

To summarize Apple's solution:


  
  Turn off the music or photo sync option in iTunes for the device.
  Click Apply to sync the changes to the device.
  Turn the music and photo sync options for the device on again.
  Click Apply again to try to sync the device to iTunes.
  If the 'Not enough free space' alert appears, continue to step 5.
  Turn off the automatic syncing functions for the iOS device. To do this:
  
  Select the iOS device from the iTunes window and click the Summary tab.
  Deselect "Automatically sync when this device is connected" and select the "Sync only checked songs and videos" checkbox.
  Click Apply to sync the changes to the device.
  Reduce the amount of data that is being synced to the device and resync the device. For example, if syncing your Music library exceeds
  the memory capacity of the device, choose "Selected playlists" to
  transfer rather than "All songs and playlists" under the Music tab in
  iTunes. If the 'Not enough free space' alert appears, continue to step
  6.
  
  Restore using iTunes.