The Policy generally doesn't (or at least didn't used to) get applied to the client's pc right away - it usually took the better part of a day and sometimes a client restart to see the new policy pushed down.
Check the Policy document properties in the clients address book, hidden $Polices view, to ensure they're updated.
Also, in order for the client to pop the warning, their last password change would have been 75 days or more ago.
I'd also check 'enforce in child policies' - just in case you have child policies.