It still reduces the potential brute force search space. Instead of forcing a clever brute forcer to search all of the horribly insecure passwords with no special characters and repeating characters, you're telling them up front that they can cut certain strings out of their search space.

I can see both sides of the argument, but often the password complexity rules result in users writing down their passwords on sticky notes. You could make the argument that if an attacker is at the desk, you're already compromised, but still it's probably better to just enforce a policy of reasonable password complexity no matter what it is. They have javascript password complexity indicators on many sites now, I think that should become standard.