... the latest Redsn0w unlocks iOS4.0.1 without any problems. I did it and it´s trouble free.
You update/restore your iPhone 3G with iOS4.0.1, then you just run Redsn0w as usual and point to the iOS4.0.0 IPSW file for the Jailbreak itself (it won´t allow the iOS4.0.1 IPSW file).
You might have some shortterm incompatibilities with Cydia apps, as some tend to be very strict on firmware versions, like Backgrounder e.g., which won´t install on iOS4.0.1 because it checks for iOS4.0.0 only.
To keep iOS4 native background wallpapers and multitasking, I strongly recommend installing iMemory VM enhancer and deleting language packs and unused launchd daemons - the 3G speed won´t scream, nevertheless shout again loud and clear, so to speak ;-)