I had the same problem... both restarting and re-jailbreaking didn't help. I originally thought it was because I had the 1.59.00 baseband on 4.1. I didn't want to upgrade my baseband, and I was ready to give up, so as a last resort I did a restore with Tiny Umbrella, then tried the jailbreak again and it worked without any hiccups. Still not sure what the issue was.