Do the following (e.g. on Nokia 6700 slide):
- Open the Application manager by selecting Menu > Settings > Settings > Applications > App. manager.
- Set Software installation to All and Online certificate check to Off.
- Retry the installation.
Check also that you have a correct date set in your device.
If the problem persists, contact the vendor of the application.