Can't call UM - Event ID 44022

Issue

Unable to call UM

Evidence

Every time a call is made to the UM server the following error is logged on the Lync server front end:-

Log Name:      Lync Server

Source:        LS Exchange Unified Messaging Routing
Date:          10/12/2013 09:27:05 PM
Event ID:      44022
Task Category: (1040)
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      lyncFE.lynclab.local
Description:
An attempt to route to an Exchange UM server failed.

The attempt failed with response code 504: exchum.lynclab.local.
Request Target: [DefaultUM@exchum.company.local], Call Id: [9f9a3df33d2544a9a22ff2c17feedcb5].
Failure occurrences: 4, since 10/12/2013 08:36:55 PM.
Cause: An attempt to route to an Exchange UM server failed because the UM server was unable to process the request or did not respond within the allotted time.
Resolution:
Check this server is correctly configured to point to the appropriate Exchange UM server. Also check whether the Exchange UM server is up and whether it in turn is also properly configured."

Solution

Make sure the dialplan is configured to use TLS (and not TCP).