Try reseting the network and setting.
I just able to unlock my iPhone 3G from Rogers (Canada phone carrier) with turbo sim that I get online.
Before getting the sim, when I slot my Maxis prepaid card, it says invalid sim. After getting the sim invalid sim becomes no sim.
After resetting for several times, no sim becomes no service (I think you're on this point) and keep reseting till I get my maxis.

Try putting your sim card on another phone and do a test call.

Hope my experience helps

Your welcome. It took me 4 freaking hour to install the freaking turbo sim .

Anyway, I don't think it actually voids warranty. My cousin who got his iPhone 3G from Fido (Roger's sister company) was able to exchange for a new one from apple store in downtown Vancouver. He said they cannot tell after you restore it.