Well, it looks like I might finally have fixed it without losing all my settings/data. But I warn you, it isn't pretty and it involved temporarily jailbreaking my phone.

First I jailbroke my phone, I used the blackra1n app, but any jailbreaking technique would work equally well.

Then I used cydia to install the OpenSSH package (again any jailbrake package installed would do).

Then I ssh'd into the phone (username = root, password = alpine).

I cd'd into /private/var/mobile/library/safeharbor and took a copy of the directory listing, so I had a note of which apps I had installed. This directory is where all the data for the apps is stored.

I then deleted the file /var/mobile/Library/Caches/com.apple.mobile.installation.plist, this is the file that keeps details of which apps are install. I then rebooted the phone.

At this point the only apps showing as installed were the Apple supplied apps, cydia and blackra1n.

I then backed up the phone. I then restored to the current firmware and let iTunes restore the backup I had just made.

So now I have a clean phone with no apps installed, but importantly I still have the settings and data for the apps I had installed. I have started reinstalling my apps and they are properly picking up their data and settings that are still there in the safeharbor directory.

I have checked that syncing of apps works and am just keeping my fingers crossed that it stays that way.

The important trick here was deleting the com.apple.mobile.installation.plist file, because then iTunes doesn't know that there were any apps installed and so doesn't start deleting the data/settings when it syncs.