It's trivial to get laws like this if you invoke one of the Four Horsemen of the Infocalypse, especially the "Think of the Children" one. Same reason why discussions of implementing Internet kill switches always focus on terrorists (and not political unrest, the only time anything like that has actually been used), and the media industry tries to tie copyright infringement to organized crime or to conflate it with counterfeiting.
I think a good rule of thumb is that if a member of the RIAA or MPAA didn't make any money from whatever you just did, they'll consider it to be infringement. They'd charge people each time they pressed a Play button if they could.
True, they couldn't automatically update the password hash on the first success. They could keep track of all of successful logins and eventually switch over after a certain number of successes. Then again, if it was 10 successful logins to convert someone other and they goofed on the 10th, they'd be locked out. So they'd have to store both the old style hash and the new one and compare both... at a certain point it would just be easier to tell the user, "you haven't changed your password in X years, please do so now."
The standard Unix & Linux library function crypt() has always only used the first 8 letters of a password in its default implementation. If they were using this function and storing only the hashed password years ago, they'd have no way to convert them to more secure algorithms until someone changed their password. Amazon probably feels that they can't force people to change their passwords without making users nervous that the company's databases has been hacked. The easiest thing to do would have been to silently update the hashed password the next time someone logged in - after several months, all of the active accounts would have been updated.