Country Lock Problem in South Korea!

I bought my iPhone 4s (Version 5.1.1) in Spain to Orange. However, I had to move to South Korea so then I asked them to unlock it, which worked fine.

I paid what I had to pay and then I did what they told me to do. I even bought a Vodafone prepaid sim card to see if it worked, and indeed it did.

Now I'm in South Korea and the people at the store tried with a Korean sim card and all I get is the "No Service" at the left upper corner on the screen (instead of the bars and the 3G). However, when I use my Vodafone (not Orange, which was my original company) simCard it detects the SKT network without any trouble. Here they told me something about country lock (of which I've never heard before), but of what I understand once you unlock your phone it should work with any company.

I hope someone can help me.

Thanks