"Network locked sim card"?

Did you try to update the phone?

Things I tried so far: I checked compatibility of frequency/bands (seems fine) and restarted the phone with SIM inserted. I'm not sure what updating the phone itself means, however.

In the Manage section of you account, there's a thing called Unblock SIM card, I don't know if that would help!

Did you try to use the PUK that you find on your Fizz account? Use it only one time.

 Updating the phone means downloading the last software Settings ->  Software update -> Check for updates.

Wheee to find your PUK code: 

1. Log into your Fizz account and go to My Plans.
2. Click on Manage and then Unblock SIM card.
3. Click the slider to reveal your PUK code.
4. Type this code into your phone to unblock your SIM.

To simplify this process in the future, write down your PUK code and keep it somewhere safe.

What ALLISON says is correct. Most Samsung phones will lock to the carrier of the first sim card you put in. A quick search, I found this: http://unlocky.net/samsung/how-to-unlock-samsung-galaxy-g... I don't know how trustworthy it is, use at your own risk.

@Code_KRUEW: I did not know that, for my A50 does not work like that, but probably is a different FW. I already inserted 3 cards without problem.

Thank you so much to everyone who answered!! You guys were right about Samsung! I had never had a locked phone but I guess it must have just locked with the first provider I'd had in there. So annoying. But resolved now. Thanks for your help!