Dude, I had EXACTLY the same prob once.
What you gotta do is download the latest version of "tiny umbrella' through google for windows mac whatever u are using.
Put your iPhone in the Recovery mode (Turn your phone off, Hold the home button while connecting the cable, the screen will be showing iTunes logo and a USB)
Open TinyUmbrella
Click save SHSHs
It will save it
Now download your 4.0.1 Firmware (its the last firmware which is jailbreakable by now)
restore it through another PC.
I tried it myself and it worked.
No need to spend money on other shops when we are here for you.