1) If you know what carrier the phone is locked to, go to the apple store and ask for a SIM card (it normally is free). They can look it up if you don't know. It doesn't need to be a live sim, just one that matches the carrier lock.
2) If it is confirmed sim locked, and you do have a matching SIM, buy an unlock from Ebay. This normally works for most US carriers from the US ebay front, and EU from the EU ebay front, etc.
3) then try a reset and activate again with a different sim to see if the unlock resolved the issue.