Security is about minimizing risk. By telling you to change your password after an attack, they are ensuring they've done their due diligence in re-securing the system. This way you can't come back and sue them for data loss after the breach, as they told you to change your password. For example, in the Target data breach recently, there were several banks that sued Target for not doing due diligence and not securing the system properly, causing fraudulent charges when they did get hacked.(1)
Included in minimizing risk is realizing that there is always some new way of getting at data, like using cloud infrastructure like Amazon to run brute-force attacks(2). If someone has the data, they will eventually figure it out, and good practice is to assume that it has been breached.
As an analogy, let's say the owner of a multi-unit building had his key-box stolen, but none of the keys were labeled. No tenant would question having the locks of the units changed, even though it would take a long time for someone to break into a unit by trying all the keys. The building owner would be held responsible if anything was stolen from the apartments until they were changed.