Presume that you have some sort of table with userIDs and password hashes (with salt). You should also consider adding some columns like:
1 - LastLoginAttemptedDateTime
2 - LastLoginAttemptedIPAddress
3 - LastSuccessfulLoginDateTime
4 - LastSuccessfulLoginIPAddress
5 - MustChagePasswordAtNextLogin - a boolean flag to indicate they must change their password. You'll set that flag when they're recovering a password, or you've emailed them a temporary password.
6 - UnsuccessfulLoginCount - some number that your logic will use to determine how long they must wait, or if they sit in the penalty box.
7 - AccountLocked - boolean flag, some pointy haired bosses will not permit accounts to be locked out, like mine. And mine refuses to allow passwords to be one-way hashes (his words: we must be able to email the user the password they use). Depending on the security you need, the user of a locked account either has to phone up an unhelp desk, or show up in person.
9 - UserAgreementDateTime - see #8
Along with a LoginTransaction table that captures attempts - both successful and not to log in, with usernames, date/time, IPaddress. This table should locked down so that a hacker can't delete entries, entries can be added, but not deleted nor changed. You'll do that with triggers ("instead of" triggers for sql server folks).
Perhaps your business logic says that a user can have 3 attempts in a 5 minute window (with no lockouts).
Your code would do something like...user has made 3rd bad attempts, set LastLoginAttemptedDateTime = Now, set UnsuccessfulLoginCount = 3.
Now the user tries to log in 1 minute later...If LastLoginAttemptedDateTime + 5_minutes < Now then log the attempt, LastLoginAttemptedDateTime = Now, reject login attempt EndIf.
If they log in successfully, log that event, set UnsuccessfulLoginCount = 0, set LastSuccessfulLoginDateTime and LastSuccessfulLoginIPAddress to the appropriate values.
This is a very real concern, however it is significantly less likely for such a horizontal attack to succeed. I recommend the grand parent post's solution for startups who aren't yet approaching critical mass and only require protection from the vertical.
Small user sets, such as the Twitter admin accounts, would not be large enough to be successful with a horizontal attack. Provided, of course, that every user has a minimum password complexity, which they did not. Even without complexity requirements, the list of simple words is still prohibitively large in most cases.
That said, if you have even one user among millions with the password "qwerty", he is certainly at risk. However, once you are at a scale prone to this kind of attack, a more sophisticated rate limiting scheme is probably required even for regular web requests.