See
http://www.greenhybrid.com/discuss/n...tery.1439.html
The recall (405) was due to an improper seal on the positive terminals. The battery is removed and all the positive terminals are cleaned then resealed. The battery is then put back into the car.
The cars would register the problem in their ECU because of the added resistance due to corrosion, but was not causing any serious problems. I would imagine the corrosion problem to be worse for cars that parked outside or in humid climates, but AFIK it was a full recall.
That's what it's all about, I'm not sure why they would say the battery was replaced, other than technically it was removed (repaired) and then replaced, but that's a minor discrepancy. As long as the Toyota folks had their hands on it your car should last for years to come.