Hmm in a way i have the same issue.
My iPhone 3GS (new bootrom) shuts down at any random battery %, even 100% after charging all night, i can't reboot it unless i plug it in, after that it'll work again for 10-15 mins depending on what i do.
I tried to fully drain and fully charge it to calibrate, but when it's completely drained and i plug it in, it'll charge starting at 40%'ish never from 0%.
My firmware is 4.3.3, jailbroken with jailbreakme. Not much installed from Cydia besides Installous, SBSettings and MyWi.
I've had this problem for about 2 months now, i tried to replace the mobilewatchdog file, but that isn't working for me either.
restored a few times without jailbreaking it, same result.
Opened it up to check if all was properly connected (even though i never dropped it..) and it was all fine.
I have bought an iPhone 4s, but as you know, there's no untethered jailbreak out yet, so i like to keep my 3GS around for certain apps. Even when it becomes available i would like to pass the 3GS on to someone else, so if there's anything else i could try (besides buying new parts) i'd like to give it a shot