Here my experiences with your suggestions:
Restart: didn't help
Reset: didn't help
Backup and restore from backup: didn't help
Backup, erase, and restore from backup: DID help! (see also http://support.apple.com/kb/HT4137).
Though: I had to reinstall the apps (which is also what I did before without success; but also without the backup-erase-restore-procedure) - now it works.
THANKS for your help.
For anyone else having this problem you may want to try my fix first to avoid a restore.
I have a 3gs Iphone too and recently carrier unlocked from the Three network, which incidentally
had the same problem of apps crashing immediately.
I tried all solutions I could find and none worked so on a whim I thaught I'd try something new.
I connected my phone to itunes on my Computer.
I then clicked FILE > Transfer purchases from iphone. "This takes a while delete any old stuff to save time"
When complete I checked the checkbox in Itunes to sync my apps and ticked the boxes for the apps i wanted"
and clicked to transfer.
Then I did one final sync down in the bottom right and my apps were working again.
Hopefully someone from apple or another user can replicate this and make a better write up on it.