Validation rules are run after the
before triggers have finished1, and there's no way to change that. It's part of the trigger order of execution.
If your before trigger is indiscriminately changing the Account Type, then of course your validation rule won't catch anything (the trigger has changed the field value away from the problematic value before the validation is executed). Your options here are to:
- check to see if the Account Type is "Other", and only change it if it is not (though this will cause the entire DML operation to fail, in normal circumstances, when you reach validation if any record is "Other")
- Rely on the validation rule to do its job when the Account Type is first being changed to "Other" (i.e. detect this change when it happens, not sometime after it happens)
The job of validation rules is to prevent bad data from being saved. If you already have bad data, you'll need to use some other tool (data loader, anonymous apex, etc...) to fix it.
1: For most objects at least, OpportunityLineItem and QuoteLineItem appear to be exceptions.