That message usually indicates that your phone was hacked or jailbroken to unlock it.
Then when you update or restored your phone it locked back up to the original carrier.
Only the carrier that the phone is locked to can unlock to.
With that said, did you purchase your phone from an authorized Apple dealer?
Was it ever locked to a different carrier?