Run the IEMSTest utility against the new users mailbox to confirm permissions.
Remove the user and try to activate and check the mailbox to ensure the ETP message arrives in the Inbox.
If it does, cancel the activation and re-add the user to the server.
Try to activate again, this time watch to see if the ETP message arrives and is deleted. If its deleted its been picked up by the Mailbox Agent and typically then you will get some sort of response. If you don't, try to activate with another SIM card/BlackBerry that you know works. It maybe a carrier provisioning issue.
...Check this KB for whole bunch more steps :p
BlackBerry Search Results