What I would do is follow the directions for preparing to restore as outlined
here.
Then restore the old iPhone and return to Apple. When you get the new iPhone, continue with the rest of the process, retore firmware, jailbreak, etc...
I would not restore from a backup. If you follow the directions i posted, you will not lose any of your data. You will need to reinstall the apps which is a good idea anyway.
I don't use MCleaner or Intelliscreen so I'm not sure how the iPhone stores the data for those apps, but I assume its in the /mobile/Library/ (fill in name of app) folders. SSh in and check for folders and what is in them. Just copy those to your desktop as well before you restore.