If you knew there was a cracker actively using your network, would you not take any other precautions other than changing the one password you know he used?

One could argue Linode was overzealous in resetting all passwords. Reasonable minds can differ.

That depends completely on the method of compromise...

If the compromise was due to a weak password that was brute forced, or obtained from the end user in some other way, then there is absolutely no need to reset every user's password.

The only time a 'reasonable mind' would think to reset everyone's password is if the attacker exploited some flaw in the underlying system, which could have given them access to arbitrary passwords.

Yeah, it does sound like there's something to the story that they aren't disclosing, and it doesn't inspire confidence.

Malicious traffic doesn't make routers burst into flame. Customers get compromised on a daily basis at any large provider due to bad SSH passwords or WordPress vulnerabilities or whatever.

Assuming the virtualization system is trustworthy (which it is), that's not a problem. Assuming it's not trustworthy, they shouldn't be running a virtual hosting company and letting random strangers sign up in the first place!

Any decently sized web host is almost certain to have crackers actively using their network at any time. AWS probably has thousands of instances running old WP installs that've been compromised.