iPhone 3GS powering off at 50%

My trusty 3GS has recently started to treat power levels of 50% (+/-
10%) as being 0% - but it doesn't give a warning, it just switches
itself off. If I immediately power it pack on it starts with the Apple
boot logo, and sometimes makes it all the way through the boot process,
but switches off again very shortly thereafter (a minute or two at most).

I've done a complete restore on it, and it's running the latest iOS

Any thoughts? It mostly gets recharged from my MacPro (which can charge
the iPad fine) but occasionally I've recharged it from the mains

"A few ground rules - no bombing, no running, no petting, no diving and
no inflatables. In fact, probably best to leave all swimming related
activities until later - this is, after all, an operating theatre."
Mac, 'Green Wing' Twitter:@GreyAreaUK