probably it was updated to a not unlockable basband which means your phone is working but with no service right ?
and no carrier options , ultrasnow wont work, oh i just finished reading your post , well since its a 3g phone and your ok with 3.1.3 software (faster ) use it or get the 4.1 os file , then via itunes press shift then restore then in the windows choose the ios file you downloaded let it restore , when it does and it turns on tell me and ill guide you , probably you will be stuck with the itunes recovery pic with a slider and emergency call ...,
iphone 3g 4.1 os link :
http://appldnld.apple.com/iPhone4/061-7932.20100908.3fgt5/iPhone1,2_4.1_8B117_Restore.ipsw
after that use redsnow to jailbreak it , once you have cydia , repeat the process with itunes but this time only tick install ipad baseband, hopefully when its done , and your phone powers ,go to cydia , manage sources, repo666.... then install ultra snow this will get your service back since you have the ipads base band , if you feel uncomfortable doing it let anyone with knowledge fix it or you will brick it .