DONT UPDATE:
Apple only allow you to update to the most recent firmware (4.1 which cannot be JB currently). The only workaround is if you have prevously JB and backed up your SHSH blobs.
You have a number of options (im assuming you have an old bootrom from being on 3.1) but none of them will land you at ios4 with a jailbreak today.
1) easiest option is to use "spirit" jailbreak, which will keep you at your current firware but will not allow you to join the jailbreak train (as its a userland JB), you will be waiting for the next exploit (greenpois0n) which will probably be out within the month but that is only a guess
2) download and run blackbreeze (which patches your itunes greater than 9.1 to allow it to work with blackra1n) then download and run blackra1n RC3 and jailbreak. This is a lower level exploit than spirit and will allow you to accept "pwned" firmware in future, i.e. to upgrade firmware to whatever apple is currently signing that has already been pre-jailbroken. HOWEVER the tools that allow this to happen (pwnage tool for mac - sn0wbreeze for windows) are not currently updated for 4.1. I believe you can hack around this by installing custom firware bundles for 4.1 on pwnage tool for mac but I have not tried this. So this option still leaves you at 3.1 but with a chance of upgrading when sn0wbreeze 2.0 is released (or if you have a friend with a mac and can get custom pwnage tool for 4.1 you can do this straight away).
3) wait for the next exploit called greenp0ison
I would go for 2 if i were you.
You will never be able to use jailbreakme.com as you will never be able to install 4.01 (the only vulnerable FW) without SHSH for that firmware which you dont have.
Warning, if you mess any of this process up, you will have to use itunes to restore to the most recent firmware, 4.1 which will leave you with no jailbreak until option 3) becomes a reality
P.s. the error messages u are having are because you are trying to update to 4.0.1 which is not allowed (not being signed by apple as its old firmware)
Good luck
--
Learntofly