OKAY GOOD NEWS for people stuggling to find a way that works for them!!! After much frustration I finally found a way that worked for me. My case was particularly bad because none of the options that were working for others would work for me. Here is what I did step by step to get third party apps working again. it requires downloading fresh copies of apps in itunes so write them all down and make sure you get all of them back. They are free if you've paid for them once already... it's a pain in the butt, but it works in the worst cases...
make sure you have latetest itunes and latest iphone OS 3.0.1 (ironic knowing that 3.0.1 was what triggered the problem in the first place for me, but none the less in the interest of thoroughness...)
1. sync your phone for a back up and sync All your apps onto the phone then disconnect it.
2. delete each and every app manually from the phone to get rid of all the hidden firmware. It's important to put them all on the phone and then delete them manually as this removes ALL the hidden firmware for all the apps that might get in the way. I read that the firmware for the apps can still be on the phone when the apps are simply unsynced so you have to put them on the phone in order to totally delete them from the phone... stupid I know...
3. do a HARD RESET of the phone by holding the sleep and home buttons until you see the apple logo and it reboots. leave it disconnected from the computer.
4. in iTunes, in the app window highlight all apps and totally delete all of them moving the files to the trash when prompted. DO NOT LEAVE THEM IN THE APPLICATIONS FOLDER, make sure you write down all the names or somehting so you can find them all again in the app store.
5. Deauthorize your computer in the store account window, close and restart itunes, and proceed to step 6, and if at the end of this procedure it doesnt work repeat entire procedure with step 5a. instead of this step...
5a. in the itunes menu bar under "store" click view account put in your password and then on the account summary page click "remove all computer authorizations". (this is what I HAD TO DO) You can only do this if you have all your five authorizations in use and you haven't used this option within the last year. You can only see/use this button once per year AND ALL your five authorizations are currently in use. I had 4 already in use and had to authorize another machine to fill up my five to get the button to show up. You can use friends computers it doesn't matter because all auths will be removed next step anyways... The point of this is that when you remove them all I think a file gets deleted/discarded on an apple server that was probably corrupted in some way. You find this button on the account summary page to the right of where it says how many computers you have authorized. Once all authorizations are removed reauthorize the itunes computer/library you are syncing your phone with. You can reauth your other machines later when your done. Reauthing them won't screw up the new file on the apple server. The single criteria between success and failure for me was removing all the auths as this didn't work the first time around when I reauthed just the one current computer. So I can't help but suspect that there is a file that gets screwed up somehow on their servers...
6. IN ITUNES... With a freshly authorized computer and an empty application folder, download all your apps again (a pain in the butt I know)
7. sync apps to the phone and they should work!!!
summary of steps
delete ALL app data from itunes and the phone
remove computer authorizations from itunes store account. (just the one your using or all of them depending on the state of your file on the apple server)
reauth computer and redownload apps in itunes and then sync them over.
It seems that the back up file for the phone has nothing to do with the problem for me at least which is good because you won't lose all your texts, notes, call history, blah blah blah. It seems to be more about computer aauthorization files stored on the apple servers, I think it's magnified by the phone OS updates but the back up file is good, so no need to worry about losing personal data!!! Maybe some of these steps aren't necessary but I'm not sure so I thought it best to tell everyone exactly what I did. Sorry if this all seems convoluted... good luck!