Errors: "An error occurred while opening the LDAP session" and "The server '<SERVERNAME>' i (4255346)

The tasks: Exchange Information Stores, Exchange Server Properties and Exchange Virtual Servers display the following errors in the logs:

"An error occurred while opening the LDAP session"
"The server '<SERVERNAME>' is not responding" (where SERVERNAME is the name of an Exchange Server)
"An error occurred while determining if the Exchange server was version 5.5"
"An error occurred while connecting to the Exchange server"
"Failed to retrieve Exchange information"

The Server Uptime Performance Counter task has the following errors in the log:

"Localizing Performance Counter library counter error '0x-2147481648' occurred"
"Localizing Performance Counter library counter error has occurred"
"Performance Counter library error has occurred"

If you try to connect to the perfmon library of the remote Exchange server from the MessageStats library the connection fails. Additionally RPC calls from the MessageStats server to servers on its own subnet are failing.