App data is stored in only two places, on your phone & in your iphone backup. When you do hit the sync button, all itunes content will be erased from your phone. Because you formatted your hard drive, your phone now sees your computer as a "new" computer & since the iphone, by design, syncs itunes content with one computer at a time, there is no way to prevent your itunes content from first being erased from your phone. If the same content is in your current itunes library, you simply sync it back. To preserve your app data, do this:
1. Disable auto sync when an ipod/iphone is connected in itunes, under preferences(under the edit menu if using windows).
2. Make sure your computer is authorized-Store>Authorize this Computer.
3. Make sure whatever contact & calendar applications you use on your computer are not empty-put fake entries in if you want, the important point is that they not be empty.
4. Connect your phone, itunes running, DO NOT SYNC, go up to File>Transfer Purchases-to make sure all purchased content is in your itunes library.
5. Right click your phone in the device pane & select "Reset Warnings"
6. Right click again and select "Backup".
7. Right click again & select "Restore from Backup". Select the backup you just made, if prompted to create another backup, decline.
8. Follow this by syncing your itunes content back to your phone, which you select, as before, from the various tabs.
If you follow these instructions, you will preserve your app data & you'll be syncing to your "new" computer.