Sim failure,invalid Sim

Hey guys,i have a problem.
I have a 16gb,sim free iphone from Italy.Yesterday i upgraded firmware to 2.2,and pwned it,and evrything went ok,but i had only one problem-i was enable to go to general setting.Every time i went there the phone would refresh and thake me back to home screen.After that i did the factory restore,on itunes,and then my problems realyy began.
The phone is not accepting my sim card (i am from Serbia),every time i insert the card, i get the message (sim failure,invalid sim,and a the end no service).I repeat the phone is sim free and he worked fine before the factory restore.
Do you have any sugestons?
Thanks

Try a DFU restore and if that doesn't works, return it

I tried DFU restore,but that didnt worked.
The phone is from Denmark,the carrier is Telia,but the package and the manual is in Italian language.So i am presuming that phones were shipped from Italy to this carrier.That is the only explanation why they were sim free.Is there maybe a chance that the phone needs a Denmark sim card for registration?