It sounds like the phone was used, or was attempted to be used, on a BES. You should not get that message from a brand new phone. Phones aren't sold by the carriers as BES vs BIS phones. Any phone can be either. I would return it and buy a known new phone from a legitimate store.
I am trying to get disconnected from the BES at work and go to strickly the BIS as email is all i really need from work anyway. But the IT guy is telling me that in order for the BIS to work there has to be a computer on all the time?? does this make sense to anyone?