It does sound like the carrier did not set it up properly.
Normally the BIS type accounts require a specific blackberry data plan to allow data including email.
Try to create an account on the Telstra BIS service for email etc. If it does not allow you to create one then I would call the carrier back
https://telstra.blackberry.com/