You need to clear your key cache.
• On a BlackBerry device: Do a battery pull
• On an Android or Secure Phone device, follow the instructions:
1. Open the app drawer and select Key management.
2. Tap Manage public keys and select the Cached tab.
3. Find and tap the user with whom you have problems communicating.
4. Tap DELETE KEY.
This will delete the key associated with the selected account. The new key will be downloaded automatically from the server.