I had the same problem and to solve it I had to hit save ssh in Tiny Umbrella itself even though Cydia listed that I had them stored there. I think the process to preserve the baseband may require a local copy of the shsh. Just click the save my shsh and it will save the 4.1 shsh to your computer and the error should go away.
With TU, you need to save SHSH files locally. Since you are trying to restore with 4.1, did you save the 4.1 SHSH files? What does it say when you click on "Display my SHSH" in TU?
I had the same problem and to solve it I had to hit save ssh in Tiny Umbrella itself even though Cydia listed that I had them stored there. I think the process to preserve the baseband may require a local copy of the shsh. Just click the save my shsh and it will save the 4.1 shsh to your computer and the error should go away.
That was the problem, no 4.1 shsh stored locally, works a treat now, many many thx!!
Apple stopped signing SHSH for 4.0.1 on August 19th (Although there were "phantom" SHSH being signed for 4.0.1 while 4.0.2 was still being signed but I think that stopped now that 4.1 is out and 4.0.2 stopped being signed)