One of the reasons I've never myself recommend using the 'Complexity On' feature in Windows Server is the sheer difficulty in trying to explain to users that you need to use characters from at least three of the following four groups:
- Special Characters
They typically switch off as soon as you get to the ...at least three.... part of the above sentence and to be honest I don't really blame them.
Even if you do head down this solution (good luck to you!) the message a user gets back when they fail to change their password successfully is fairly generic and does not even mention the fact that complexity is in use.
However, today I was made aware of a hotfix for Windows 2003 (and associated clients) where the user will now see mention of complexity requirements in the message they receive back. Since I've never heard or seen anyone else using this before I thought it was worth mentioning since it might make your deployment a bit smoother.
I've yet to test this out myself, but I guess you gotta trust the KB article ;-)