Facebook stores old password hashes (along with the old salt), such that if you try to log in with a previous password, Facebook tells you that you updated the password (and when). Nice user experience. Except this site isn't ux.stackexchange.com.
So, what security threats are presented by this?
See also about Facebook storing old passwords here and here.
The other answers look pretty reasonable, but I wanted to add a few possibilities.
If an attacker recovers one or more of your passwords from other breaches, it seems like plugging them into Facebook's UI could leak at least a few types of information:
If pattern-matching on recovered passwords suggests a likely iterator or mutation pattern in your password, it also seems like an attacker could also try one or two passwords they haven't seen in order to support or refute a thesis about how your passwords evolve over time.
I would guess any attacker is somewhat limited in how many such tests they could attempt without someone noticing, but it seems like information along these lines could inform heuristics for how known users change their passwords, improve statistics on how common different update patterns are, and help hone priority lists of users/accounts that are most vulnerable.
These seem like fairly small risks at the individual level, but it also seems like (Martin Bos' post on cracking hashes in the LinkedIn breach is instructive) small heuristic improvements turn into pretty nice levers for recovering more passwords in a large scale breach while simultaneously improving the heuristic/lever.
This is also done by systems that block you from re-using passwords. If, for example, in Windows you require monthly password changes and require that no password be re-used from the past year, the password file will contain your current password hash + the 11 previous ones.
It is a security risk if the password hashes fall into the wrong hands and are cracked, if anyone used their previous password on any other sites. A user may reasonably expect that a password is gone from the database after (s)he has changed it.
TL;DR The security risk is only increased in the event of a database breach where the older passwords are stored on a Weaker Work Factor
One more thing, is straight theft of a password via a virus on the victim's computer. It could be helpful to know for sure that the password was once valid, and then to try some variations on this, but this would only have limited effect as this attack is probably going to then require Online Brute Force which will probably fail.
A site of this importance should already be using a Secure Password Hash such as BCrypt already w/ appropriate Salt & Pepper.
In this case, if the hashes are compromised, then the attacker would next have to Brute Force a multitude of possible passwords, so that the original password could be determined. This may take a long time if the password has a decent level of entropy. However, some users are lazy, and will use simple passwords. Those will be cracked first.
There are two types of brute force to consider.
Online Brute Force, which typically will not get you very far. The site's public servers should only allow you to try a limited number of passwords in a given time period before Captcha is presented, severely limiting the number of possible passwords that can be attempted.
There should be additional layers of security as well. For example, if enough Captcha-authorized attempts continue to fail, then they should lock down the account or block that IP.
So there's probably no additional security risk to this type of attack.
Offline Brute Force is when the database is comprimised and the hashes are stolen. In this case, not only do the latest hashes leak, but the older ones as well, because, as you say, those were not erased.
In this case, there is also no additional security risk because cracking the older hashes will serve no purpose.
An exception to this is if the Work Factor was adjusted. The older passwords may be stored on a weaker Work Factor, in which case the attacker would crack the older one first, and use that as a potential hint to crack the latest password.
Once an offline hash is brute-forced, that password would be used by an attacker to gain access to either the main site's account, or try other sites (i.e. Email or Online Banking) where the user may have re-used that same password. (so don't re-use passwords)
The increased risk regarding the service in question is at most comparable to
Regarding other services, the risk is only increased if one of the old passwords is still valid for another service, which you should not do anyway.
However, if said service makes the old passwords valid for some use (e.g., allows an old password as authentication in a lost-password process) the risk grows dramatically.
