Even if attackers had full access to systems, shouldn't properly encrypted user passwords (e.g. bcrypt with high cost) still be completely safe? Don't we trust the encryption?
1. It's in the title: "Assuming proper". Unless the company can prove it was always proper, that there are no copies of a old schemes in backups, that there was no ongoing migration of old data (from unsalted hash to bcrypt), and many other situations - it's safer to just reset than assume anything.
2. How deep was the breach: Is there any chance incoming requests have been captured? It doesn't matter how strong the hash cost is, if there's any possibility that the attacker had access to the incoming requests after tls layer is stripped. It may not even be obvious at first - simple sql injections may allow file writes on some complex system - you could escalate from there.
(for the same reason they should also kill all existing sessions, not just change the credentials)
3. The most complex hashing scheme doesn't help if some users have password "password". Let's say the hash is salted and complex enough that it takes 1 second to verify each guess and that you've got a dump of 1M accounts. You're unlikely to crack many, but that's not the problem. Take 3 most common passwords ("password", "123456", "qwerty", or similar) and check each account against them. Even serialized one-at-a-time check will only take a month and you're almost guaranteed to find a few accounts that match. (of course that may not be worth doing in each case - depends on how important gaining the access / accounts are for you)
That said, the risk of something very costly (losing data) is still greater than the guarantee of something not-very-costly (changing passwords), so changing passwords is a good idea.