From what it looks like, yes, it really does take a new battery. Which is why it must not be an easy fix. It's not as if we didn't expect battery engineering to get better. I feel a twinge of disappointment, but I don't feel like it's 'owed' to me or anything like that. It's not something that went wrong in my car. It's just that technology improved. Personally, it just makes me even more excited for the next generation.
I think we'd all expect batteries to improve by Model S 2.0, but certainly not within the first few months of production. Battery technologies improve over the course of years, not months.
All we know at this point is that it is something related to the battery. Might not be the entire pack that needs replacement so let's not jump to conclusions.