Let's consider Adobe, since we have actual data. Of 130,324,429 users, we know 1,911,938 chose the password '123456'. Consider just that population of users.
Assume a 64-bit salt was chosen uniformly at random for each user. The probability that this cryptosystem is catastrophically broken (i.e. leaks password equality between users in just this population) is about 2^-23. That's not good -- usually cryptosystems are designed to have a probability of failure between 2^-80 and 2^-256. Now multiply that up for each population of users choosing the same password, and you're in trouble.
Adding in other user-unique data is definitely a good idea!
> is about 2^-23. That's not good -- usually cryptosystems are designed to have a probability of failure between 2^-80 and 2^-256.
The failure cases are different though. Cryptosystems that require a strength of 80 to 256 bits are measuring their strength against an adversary brute-forcing or performing some other active discovery.
In this case, it's just the probability that two users will pick the same password and get the same salt. The attacker doesn't get to run many guesses, the database is just leaked 'as-is' and the hashes either show equality or they don't. So there is only a 1 in ~8mil chance that two in that group will show equality. Not bad for such a large population.
It doesn't then multiply up for each population. It's a sum since they are independent groups. Even then, the probability for each subsequent group will be vastly smaller as the population size decreases.
Finally, the only population at risk is users that chose such blindingly obvious passwords that they ended up in a large password population pool. These would be the same accounts that would be revealed almost immediately anyway since the obvious passwords is where any brute-forcing tool worth its salt (pun intended) would guess first.
Assume a 64-bit salt was chosen uniformly at random for each user. The probability that this cryptosystem is catastrophically broken (i.e. leaks password equality between users in just this population) is about 2^-23. That's not good -- usually cryptosystems are designed to have a probability of failure between 2^-80 and 2^-256. Now multiply that up for each population of users choosing the same password, and you're in trouble.
Adding in other user-unique data is definitely a good idea!