Why would the attacker, if they got the passwords, not bother to look to the column just to the right and take the salts as well? Given that, the attacker can try hundreds of billions of password combinations per second.
What I am saying that if the attacker gets a row from the database that has the user's id, the password will be in a column labeled 'password'. Next column is likely to be the salt generated for that user's password, and let's say that this column name is 'salt'. With the salt and password for each user, you can run a dictionary across each combination at a furious rate.
25 late 2012 vintage GPUs gets you 180 billion MD5 tries per second. With a fairly modest budget you can rent a whole lot more GPU power than that. A little Googling gets me several companies offering password hash cracking as a service.
But we're assuming, at the very least, that they're not using MD5 and are instead using SHA-2/SHA-256 or (s|b)crypt.
There's an order of magnitude difference between brute forcing MD5 and brute forcing something better.
MD5 is 2-3x as fast as SHA-1
MD5 is 5-7x as fast as SHA-256
I don't know why anyone would assume they are using anything better than MD5/SHA-1 considering the history of incidents like this.
Shocker!