What version of UCM are you running?
Is the SIP trunk set to require an MTP and if so, does the gateway's MRGL have one available?
What protocol (MGCP, H323, SIP) is the PSTN gateway running?
Is there a common supported codec between the voice gateway and the Vocera server?
Have you collected logs from UCM (detailed level) to see what the signaling shows?
Does UCM ever send an INVITE to Vocera? If so, where does the dialog fail?