unlock problem iphone 3GS

[hel22]

I hope someone can help me here.
I bought an "unlocked,jailbroken" iphone on ebay.(fw 4.3.2) I live in Europe. So when I tried to put my sim card in, it keeps saying searching or invalid sim. I guess that means that the phone is locked...
Im so annoyed bc the baseband is 05.16.02 which cant be unlocked..
Now a few questions..the guy claimed his friend unlocked it for him.

1. I checked cydia and I see ultrasn0w is installed, what does that mean? Does that mean he did unlock it and maybe i relocked it by mistake?
when I connected the new phone to itunes, it asked me if I want to set it up as a new iphone or restore from backup so I restored from a backup, could that have locked the device? OR since it has baseband 05.16.02 it wasnt unlockable to begin with?

I first have to know if its my fault or the guys fault.
Any help is appreciated!

[Poseidon79]

He lied. 5.16 is not an unlockable baseband with ultrasn0w... sorry. Your only option is to use redsn0w to flash the ipad 6.15 baseband in order to unlock.

[Jcbzr]

You got scammed. If you're in desperate need of an unlock, I suggest you flash the iPad baseband... it's your only hope.

[hel22]

Thanks, apparently the one who sold it was told so by his friend who supposedly unlocked it for him, I think he was telling the truth since I asked what was used to unlock the phone he said redsn0w (which is a JB) so he doesnt know much about these things.
Ok now onto my problem, I see I really dont have another choice bc otherwise the phone is useless but Im upset about the GPS since I was planning to use it...
Now my questions.
1.How do I know with what he jailbroke it? and in order to flash baseband, do i have to restore the phone and then rejailbreak it? or can I proceed like that? (Have no clue how to do it) and if I restore it, does there exist a untethered JB for the latest firmware? 4.3.3? I now have 4.3.2

Thanks for all help I can get :-)