Are you able to connect the device to the BES and assign the device?

Also, have you spoken to your provider whether the device is provisioned correctly?
(It's always the first thing I check)