How should I store my users passwords in my DB?
For practical reasons, I don't want to make them choose enormous passwords - but I do at least want to prevent permutation attacks picking them off in under 1 second each still!

use salted, highly iterated password hashes, preferably utilizing PBKDF2 or scrypt.
You should use a good, stretched password hashing function like PBKDF2 (perhaps with SHA512), bcrypt, or scrypt. You MUST have a unique, per-user salt (those functions require it).

If you use PBKDF2, use a sane iteration count. 1 is not sane. Benchmark it on your system and find out how long it takes, and tune it to around 5ms. You up your risk of login-based denial of service slightly, but your passwords are quite secure at that point.

What language is it being written in? If PHP, there's a quite good library here:
1) Don't enforce a short maximum length - you're storing a hash, so if they want to use an epic passpoem, let them. The lower the number of scrypt or PBKDF2 iterations, the longer the minimum length you should use. I'd say 12 to 14 is a reasonable minimum these days for low security sites.

2) Recommend passphrases. If you really must, auto-generate a set of cryptographically random passwords and offer them as options

3) Check the cleartext of what the user proposes using against a basic dictionary and basic rules. The common responses to "10 character minimum, upper, lower, number, and symbols all required" are "P@$$w0rd123" or "Jennifer1995!", both of which Hashcat will select near-instantly from even very small password lists using rules. Ideally, you want to prohibit users from at least most of the passwords that Hashcat will find with Best64 rules and the phpbb wordlist.

4) Follow the advice above; scrypt or PBKDF2 with large numbers of iterations; OWASP currently recommends 64,000 iterations in 2012, and will recommend 128,000 in 2014.

5) Use a variable number of iterations. Just like the (large, 64 bits or higher) salt is very likely different for every password stored, have a very likely different number of iterations for every password stored. For example, in 2012, use 64000+rand(32000), and save that number of iterations along with the salt.

6) If you're in a regulated industry (health care, finance, criminal justice), check national, regional, and local regulations and laws - you may be restricted to certain algorithms and minimums and so on and so forth.

7) Implement some kind of checking for online attacks; if you get N thousand failed logins per M seconds regardless of which usernames are involved... is that normal peak load, or did someone's distributed botnet pick you as a target?
One discussion I've had recently with some people for online attacks is to limit both per-IP attempts per second, and per-username attempts per second, with the limit being tripped causing an "automatic reject."

Don't tell the bot that you've caught it. Just let it sail through the right password without you bothering to tell it that it's succeeded.