http://crave.cnet.co.uk/mobiles/samsung-says-galaxy-s4-battery-woes-limited-offers-free-batteries-50012509/
This is a known issue and Samsung in NZ have been very cagey about how widespread the issue is but have announced (overseas) they will replace batteries at service centres if they exhibit this issue. I was quoted a serial number range of BD1D401xx - BD1D529xx as an affected range by Samsung NZ support, however that was only after being quite insistent.
The person I spoke to at Samsung NZ was very reticent about acknowledging that it was a known issue. This battery is only about 5 months old.


I'll update with how co-operative Samsung NZ are now that I have sent them all the info they asked for. Their opening gambit was "Take the phone to the retialer or a Telecom store and they'll send it away for inspection". I was pretty insistent that while that approach may satisfy the requirements of the CGA and warranty, that would be enough to ensure I never bought another Samsung Anything - especially given this is a known issue (and my battery SN was in the affected range I was quoted)
Cheers _ N


