Random Shutdown Syndrome only when battery is connected

My MB has developed the 'Random Shutdown Syndrome', but only when the battery is connected.

It runs fine with the magsafe connected and the battery physically removed.

With the magsafe, and battery both connected, it will boot, but will go off randomly, sometimes before boot is complete, sometimes will last up to a couple of minutes.

With the battery only connected, it is completely dead!

The battery is new, and completed 1 charge cycle before this problem occurred. It is still showing fully charged by the green lights on the back, and is being recognised by the system profiler when I can get it to stay on long enough to check.

I have replaced the battery connector, but this has not fixed anything.

I have also replaced the HDD and reinstalled all software from scratch, so this is definitely a hardware issue.

Any help would be much appreciated. Thanks.