First possibility: Your phone is locked to a particular network/carrier, and you have a sim from a different network in it. You'll either have to get the phone properly unlocked, or you'll need to get a sim card from the network to which the phone is locked. Since you say you haven't entered a bad PIN number, this is my first guess as to what's going on.
Second possibility: You've locked your phone, and it will require a PUK code to be unlocked. You'll need to get your carrier to generate a PUK code for you; it's based on the sim card. When you get the PUK code, be ready with a new SECURITY code, because your phone will ask you to supply a new one. DO NOT keep guessing; if you put an incorrect PUK code in enough times, it will fry the sim completely; it will be permanantly disabled and you'll end up having to buy a new one. It will NOT harm the phone.
I unlock several of these a day; it's not a big deal, but it can be a hassle if you end up having to get a new sim card.