Do the following (e.g. on Nokia 6700 slide):

  1. Open the Application manager by selecting Menu > Settings > Settings > Applications > App. manager.
  2. Set Software installation to All and Online certificate check to Off.
  3. 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.