Alright , this is what you have to do, I will give you an activated 4.1 custom fw . You have to download the stock 4.1 and redsn0w 0.9.6b2. Run redsn0w first and browse to stock 4.1, check only the box DFU mode, once you are in DFU , open up itunes and shift + restore to this custom fw of 4.1 which i will send it to you over Private message.
Just tried to re-jailbreak following your instructions but redsn0w wouldn't recognise my stock 4.1 ipsw.
So I put the phone into a jailbreak state using iREB and then restored to the custom firmware you sent. All has worked great from a jailbreak point of view, Cydia open's and updates. I did this at home all via wi-fi, nut now I have left the house I no longer get a network, no 3G, no Edge and not able to make calls!
Any ideas? Try again? Or is it something to do with the custome ipsw you sent me the link for as the title says 3GS and mine is a 3G?