This is weird. I thought I am the only one having this issue. I just upgraded my iPhone 3gs to 4.3.1 on mac with Pwnage Tool 4.2. It appears to be untethered! This is a video that I found from a guy having the same untethered issue.
According to Taimur Asad from Redmondpie, he mentioned that the jailbreak is tethered, and “use tetheredboot utility to boot your device in a jailbroken state on every reboot/restart”. I am being able to restart my iPhone without using Tetherboot or any other boot utility.
If you are interested in jailbreaking your iPhone on 4.1.3, and see for yourself. Follow the guide below