** significantly updated my answer as it contained a wrong assumption **

Validation rules will not run after a field update (credits to Amit. See his answer for a full explanation).

So you have to do the validations before scheduling the update. Do note that on every new update of the record, the workflow rules are evaluated again and if the conditions are no longer met, the scheduled field update is revoked. So theoretically the update will then never happen if the record does not meet the conditions. However, this is *not* valid if the conditions consist of data on related records.

Validations in apex triggers WILL run after a field update, so they will block the update and leave the record unchanged. In this case you can also build in a notification mechanism that the update failed, e.g. send out an email or insert a record into a logging table.

All in all the safest way to do this would be via an apex trigger, including a notification mechanism.

FYI some earlier discussion on this subject here:
http://salesforce.stackexchange.com/questions/22791/bests-practices-for-handling-potential-errors-as-a-result-of-time-based-workflow?rq=1