I've had this happen when the PIN wasn't registered already. A customer of mine bought an 8830 World Edition and had it unlocked for use with Usacell in Mexico (they didn't carry Blackberries newer than the 8700 series and he wanted one). When he tried to activate the PIN on his carrier, he got that message. It was a brand new phone and when he brought it back unused it was resold in the US without a problem.