Mobile network not available I have serious problem with my Galaxy S2.

Some guy stole my phone. With help from Samsung Dive, I gained his phone number because he put his Sim card in my phone. Then, with help from police, I got my phone back. Just today, I went to shop for a new Sim card because my old one was lost (thanks to that guy!). First, I did factory reset without any Sim card inserted. Then I put in my new Sim card in it. Here comes the problem - it doesn't recognize my Sim card! First I thought that I did put it in somehow wrong, but after few tries - I think that it isn't the case. I remembered that it asked me something about missing Sim card when i booted up phone after factory reset so I did factory reset again with Sim card in it. Still, problem remains. When I try to call someone it says Mobile network not available. When I try to select my network operator under settings, it says Unable to connect. Try later.

What could be the problem? Is it possible that my phone is blocked? If so, where can I unblock it?

Thanks for any advice!

P.S. Are there any steps to find why I cannot connect to mobile network?

Edit:

When turning the phone on, it shows yellow warning icon.

When phone is on, near clock in top bar there is like phone icon.

If that anyhow helps, guys!
Provider did block the IMEI of the phone. Now it's unblocked and all works fine!

Thanks to Matthew Read for clue... :)