A couple things just off the top of my head ...

* Detect that a login occurred from an unrecognized IP and email the account holder to tip them off.

* More stringent password requirements and a check against public leaked database registries to alert the user that the password they're using has been leaked.

But it seems like the bigger frustration is not that they did not prevent it, but that when it occurred it was difficult to raise the issue, and the response was tremendously inadequate.