Which should be done, but which doesn't help those users where it matters most; the real value of this database is that some people (~everyone) reuses passwords across sites.

And send them a note too, sure. They've got their e-mail addresses as well so a note of apology and warning is certainly in order.

From the looks of it, the data dump may be all accounts - since there seems to be no salt, and many people use same passwords...