If you let them know what kind of a password is expected of them from the get-go
your life will be much easier. At school, our passwords couldn't be (or contain) dictionary words, and they had to include some sort of punctuation/caps/numbers. We also couldn't use numbers as letters to form a word (e.g. m0m or d4d), and we had to change passwords frequently and couldn't use anything even similar
to one we had used previously. It was kind of tough at first, but no one really complained because we knew from the start.