Off the top of my head:
Make sure that the iPhone software is up to date with the latest version. Make sure the app you are using is approved for the version of software you are running (check the app on the app store).
If you have tried removing the app and reinstalling it through iTunes, the next logical step would be to backup data nd Restore the iPhone software, then try to reinstall the app and see if it works. If not, then you'd probably have to hit up the developer of the app.

Reply With Quote