The reason why this question is more complex than it first might appear is that user chosen passwords are subject to human factors and specifically the habit of people to choose passwords that are memorable and as simple as possible even given complexity requirements i.e. users are smart at finding passwords that meet complexity requirements but are actually from a more guessable set.
If you give a lot of information away about why a password attempt has failed then from a purely mathematical point of view you can overcome this by increasing complexity requirements, but this doesn't take into account user behaviour which may negate the additional complexity.
Brute forcing can be guided, and increasing (for example) password length doesn't necessarily provide the apparent key space to search because heuristics still apply. Also remember that complexity requirements can reduce the key space from the maximum space that is just based on length - at least heuristically. Think of the old complexity requirement to use at least one digit and users just appending a 1 on the end of their favourite password! Easy to create heuristic based password guess algorithms for - this doesn't increase the key space by an additional character set in reality.
Having said this I'd live with the risk if the complexity increase was substantial and the complexity requirements weren't too simplistic or easy to circumvent in some way.