Is this a brand new peal or did you buy it from someone? Chances are if you bought it from someone and your getting that message then RIM blacklisted your phone as it was reported stolen at some point. Your best bet is to call RIM directly and give them your pin number and they call tell you any information they have on it.
Posted from my CrackBerry at wapforums.crackberry.com