Given that they've requested you to change password to conform to the new rule, I believe you were within these 99%? ;)
I am curious what simple pattern people will adapt to once you eliminate simple sequences. It has got to be predictable, as in someone could put math behind it.
I'm of the opinion that everybody should be given public and private key at birth.
edit: On second look, that's exactly what you did in your example.