For now, the unlock for 3.1.3 has not been released but will be released when the iOS 4 hits the market. So you may have to wait a bit. Also in future, if you need to keep a phone unlocked, resist the urge to upgrade to the newest firmware for Apple.
Also, iOS 4 for the 3GS may be jail-broken and unlocked as soon as it hits the market. If that happens, you will simply upgrade to iOS 4 and then unlock.
For now it is wait and see.