Maybe just a minimum length? I too get annoyed when there are specific complexity requirements, like 'must include an uppercase letter' even though I've used a 20-character long password including numbers and punctuation.
I did come across a site that had a cuss word filter, then wouldn't let me change my password... lol. No mention of why it was an invalid password.
If you must have certain complexity requirements, spell them out. Personally, if it's over 8-10 characters (with leading and trailing whitespace trimmed off), I'll take anything... convert to UTF8 bytes before 1-way hashing...
As for using SCrypt, if it takes a modern CPU 1/2 second on a process to hash a password, then that's ripe for a DDOS against your authentication server, which is where failed attempt counts, and locking for X minutes comes in.
More generally, you could ban the top X passwords from those "most frequently use password" lists.