It can only be one of three things: The SIM, the device , or how the service is set up with your carrier.
Sounds like you have proven the SIM isn't the problem.
Maybe if you can contact your carrier to verify how your service is set up, there will be something that will come to light.
If not, you can safely assume it is a a defective BlackBerry.
1st Step in Troubleshooting: Do you have a BlackBerry Data Plan?
2nd Step in Troubleshooting: Pull the Battery.