The criteria is not checked again in this situation - see below
According to the Time-Based Workflow FAQ, any record which no longer matches the criteria for a time-based workflow will be removed from the queue. This is vague though and doesn't indicate whether a test is performed if the other record is updated.
I would expect that the criteria would work like a formula field, and that the system would at least check for validity when the timer elapses before executing anything, discarding the record in the process - but it seems like I am wrong.
Test Results
I ran a test to see if the criteria would be evaluated again before the workflow actions took place, and it seems like no check is performed.
When changing a field on the second object such that the criteria would not be met, the first record stayed in the queue which is to be expected.
However, the field update I specified was still performed once the time-based rule was processed.
Work Around
If you update the record that's queued such that it doesn't meet the criteria for the work flow, it is removed from the queue. An extention of this is that if you modify object B so that A would fail and then perform a non-changing edit on A (i.e. hit edit and then save) it also gets removed on the queue.
The upshot is that you could create a trigger on B after update, to perform a non-changing edit on all child records (object A) of the records being run through the trigger. This should in turn clear out the non-conforming records from the queue and prevent the workflow field updates etc. from taking place.