NO. Getting a new sim card will not unlock the phone.
The message that you have is that this sim card is not supported in the phone, which actually means that your phone is locked to the carrier.
Which carrier did you use with the phone originally? Did you hack the phone to unlock it? You might have done, because if you hack a phone to unlock it, then as soon as you restore the phone, it will re-lock to the original carrier of the phone and it does not remain unlocked in the same way as it would do if you had approached the carrier to unlock it for you.
You need to find out who the carrier of the phone is and then go and get a new sim card and see if that works in the phone. You then need to approach that carrier and request that they unlock the phone for you.
Only the carrier of the phone can unlock it for you - nobody else and Apple cannot either. Anything else amounts to hacking the phone.