In fact, as you can see in the picture I do have WiFi Sync installed ;] ill uninstall that as well.
That was the only problem, nothing else was causing the issue.
This is a known issue with WiFi sync and one of the main reasons the app store didn't approve it.
I guarentee you removing it from your computer and then restoring will work. You can install the application on the iphone after. Just remember if you restore your iPhone, you must remove the application from your computer and restart first.