Don't do Restore to the latest Firmware, it will ruin the unlock of baseband.
What is your iOS number (4.0.1) and your baseband number?
Check redmondpie for unlock it. Usually the unlocking and jailbreak is done with Restore to a specific firmware, not the default latest version.
On the other hand, once jailbreak and unlock, it should be able to link to iTunes, at least two years ago it can. :) Maybe someone from Apple patched the hole and auto detect if an 3Gs is jailbroken.
Well, you may dump iTunes totally, since your Apps phurchases are stored in iCloud anyway. Since your phone is jailbroken, you can use a Linux or Mac to SSH log in and SFTP everything out!
