i just read the article you mentioned. and i'm not sure that you've taken away from it what was intended. the basic concept of the article states that the longer the password, the harder it will be to crack as you're adding more possible options to the password.
basically the studies have shown that a moderately complex 12 character password that's not a word from the dictionary is the strongest (as with modern technology it would take a couple thousand years to crack). however it's difficult for a user to remember a 12 character word that's not in the dictionary. so instead you can make a 12 character phrase, as one word that would be equally (roughly) as safe as an 8 character random password
so in your last example:
ThelegendoftheFalls would actually be a fine password as it is. (though changing some of the letters to numbers or special characters would be better) it would take an immense ammount of time to actually come across that combination of words randomly through normal password breaking methods.
1. Ensure that if the new password is not accepted, the pop up should give the conflict with the particular policy for which the password failed.
in a windows domain, when you set strong password requirements, a popup is displayed....though it does give a more general explanation, it does list out what the current policy requires. strong password requirement on the domain means that the password has to be of a certain length (which isn't specifically mentioned in the prompt but your own company policy should be clear to the employees), and the password must contain certain character types (the prompt DOES highlight this requirement specifically). so as long as your password policy is known through out the company and explained before a user ever sets their own password, any issues are purely human error and not something that will be very easy to account for.
most employees, management especially, hate anything that makes them have to work a little harder, or think about something before they do it. they want to press print and have the paper show up on the printer on their desk instead of having to walk 10 feet to a shared printer. the only way to NOT have employees complain about a password policy is to not have one. period.
at a previous job (hospital) people complained about the password requirements so much before i ever got a logon that i was actually concerned about the policy being too difficult. once i finally got access i found out that the only requirement was that the password be 8 characters long and that you had to change your password every 6 months. there was no complexity requirement and no password history, so at most you had to remember 2 passwords and just alternate between the two twice a year.
the only way to actually fix this issue is to educate your employees and management to the importance of security and that a password is the first line of deffense