Carlos,
What version of Exchange are you running? 2010?
Is your UM server separate from your other servers? If so, the problem is likely with Receive connectors not letting messages from UM be admitted to the Hub Transport queues.
Another problem could be certificates used for UM aren't trusted by the rest of the Exchange infrastructure. Did you issue a UM cert from your internal CA?
Hope this helps,
Gonzalo