Error when testing connection:"An error occurred when verifying security for the message" (4275918)

Unable to connect to the Notes Migrator for SharePoint (NMSP) Import Service at 'http:server:port/ImportSession.svc' due to the following error: 'An error occurred when verifying security for the message.

The issue can be possibly caused by time difference between NMSP console and the  target server having the NMSP services installed (time is not synchronized) or insufficient permissions of the  NMSP Import Service identity

Please check if the time is synchronized on both machines involved  and test the NMSP sevices configuration at Central Admin page |  Application Management  | Configure Notes Migrator for SharePoint Services |  Test this configuration and resolve the resulting permissions issues if any.