Ouch. I had the exact same thing happen with my iPod Touch. Same error code. I never solved the problem, so I'm sorry I can't help. I tried for WEEKS to solve it and I never found a solution. If you do, please let me know - and good luck!
There may be other solutions, but strictly using itunes or Xcode you probably will never be able to go back down from 4 to 3x as the baseband is upgraded in the original upgrade.