WFFM only supports client-side validation when using regular expression-based validation or otherwise native validations (updated 6/29). Custom validations beyond that is something that you need to add on your own. However, it does include native support for custom server-side validation (updated 6/29). From your description, it sounds like you have the server-side validation set up in Sitecore, but you are missing the client-side validation.
UPDATE 6/29: Clarifications, as requested
Re-reading this post, @jrap is correct that the wording was confusing. The following is meant to clarify the post.
WFFM does include client-side validation for its built-in form-specific, field-type validations (including the "Custom" validation) and required field validator. However, the use of these validations is somewhat limited, with the field-type validations applying to all fields of a particular type that use it and the form-specific validations being specific to a field but only supporting regular expressions. This means that if you have a more complex validation, e.g. checking to see if a chosen date is within a predefined range, then these validation features are somewhat limiting. In these cases, your best bet is often to write your own custom field-type validators. You can specify error messages and your logic, but you will still need to add your own custom client-side validation. This is because custom field-type validators are server-side and thus validation is only triggered when the form posts to the server. If the field is invalid then the form will display again with the necessary validations. However, client-side validation can be used here if you want to prevent the form from being submitted if invalid.