To answer your question about what you lose when you restore as new:
You don't lose paid apps. They remain in your purchased list. You do have to download all your apps again. If you don't have your photos on your computer or in cloud based apps like Box and Dropbox, you will lose those. You will lose messages. If you have widgets set up in the Notification Center, you'll have to set those back up. If your notes are on iCloud, you should not lose those. You won't lose Calendar events, Reminders, and bookmarks in Safari. Keychain will be safe. It's a PITA to do, but it sure helps sometimes.