I think this customer needs to be beaten over the head a little. :)
The annoying thing is that I can understand and even empathise with where they're coming from. But this requirement will only cause grief and hassle in the long term (I can see, for example, a future requirement for the list of "known common passwords" to be updated on an annual - or even more frequent - basis). Password complexity requirements are known to work in the field, and even the most basic complexity requirement (such as any 3 of uppercase, lowercase, numeric or symbol) will automatically exclude the vast majority of dictionary words.
Another deal breaker is that a lot of people will use things that they are familiar with as a password. A social security number, for example, might meet a complexity requirement (numbers, letters, and a hyphen, perhaps), and would certainly never be in any hypothetical list of "known common passwords", but would also be un-secure in that it's one of the things a potential cracker would try (assuming that they either knew it or had the means to obtain it).
One online service I used once gauged password security by measuring a combination of factors: how many of each type of character was in the password, and how long the overall password was. Instant feedback was given, so you could get a good feel on whether your password was deemed good or not based on their metrics. Such an approach seems much preferable to me.
Also attractive would be using a service such as OpenID or Microsoft Passport (or whatever it's called this week) instead of implementing your own. I'm massively suspicious of services that require a user to have a separate logon for everything they access. The major risk is that the user has so many username/password combos to remember that they will end up writing them down, and also that they will end up using the same username and password for them all, so that if one - and all it takes is one - gets compromised, they're all effectively compromised. The weakest link rule applies here with knobs on. Going with a provider who specialises in this area is a Good Thing (you're free to focus on specifics of your service, you have an authentication mechanism that's known-good, etc).