On the one hand, the complexity rules are probably not good. On the other hand, your “nonsense words” may not be as complex as you think.
There is no “presumably” about ease of brute force: this can be measured. For a given attacker, the cost of a brute-force attack is the average number of attempts before finding a password. While you don't know your attacker, you can assume that he is smart and will build his attack around your password choice methods. (It's the smartest attackers you need to most defend against anyway.) What the attacker will definitely not know is the part that you pick at random for every password. The amount of randomness in a password is called entropy; it is the number of coins that are flipped to determine the password, expressed in bits. The entropy also measures the number of brute force attempts that a smart attacker will require: with n bits of entropy, there are 2n possible passwords, and the attacker will on average need to try half of that, 2n-1.
Requiring punctuation, digits or uppercase letter is common, but it doesn't help security much. Just about every user who would have picked a dictionary word as a password capitalizes the first letter and adds a
1 at the end. People who crack passwords aren't stupid: they include this and other l33tspeak variations in their cracking dictionaries. All in all, this requirement may add one or two bits of entropy in practice. There are better ways to make memorable passwords with more entropy.
This is illustrated in xkcd 936 and discussed on this site in XKCD #936: Short complex password, or long dictionary passphrase? (warning: skip Jeff Atwood's answer, even though it is currently the top-scoring one, because he blithely ignores the math).
Rather than presuming the strength of your nonsense word generator, you should measure it. Figure out how it generates passwords, and more precisely what the total number of possible passwords is. We can't tell from a single example. If the generator alternates 5 random vowels (presumably
u) with 20 random consonant groups proper(
st,…), that makes (5*20)5 = 1010 ≈ 233. Assuming your passwords are properly protected, that's plenty for online attacks and ok for offline attacks. (If you aren't using a sufficiently slow hash, 33 bits is peanuts.) If the password generator is combining fragments of words from a dictionary, the entropy may be a lot less.
If you aren't in a position to lift the password complexity rules, issue passwords that comply. Make studies to see if they can remember one capital letter and one digit per password; if they can't, always capitalize the first letter and put a trailing 1.