In addition to the frustrations you've outlined, consider a further case where a user's username is their email address (this was true in the project I mentioned). How is the user most likely to behave in this scenario? Are they going to take the time to generate a new password that satisfies your constraints, or are they going to keep things familiar and use the same password that they use for their email? Afterall, the usernames are the same - so why not keep things easy to remember? Well, I'm sure that's convenient, but I absolutely DO NOT want your email password, even bcrypted/&c., in my DB. No thanks.
Clearly, then, the best choice is to generate something for the user; something that they can reset using a classic 'forgot password' system, but which they never have to define themselves. Four diceware generated words, plus spaces, each no longer than two syllables, seems to do just fine.