O2 sensors are "wear" type of devices. Unlike some parts, they have a finite life; ~100k miles is what I have read. Two that are the same age will have seen virtually the same variables over the years; mileage, type of fuel, fuel additives, heat cycles, and all the things that cause them to wear out. Therefore, if one is bad from normal wear, then it seems logical that the other is not far behind. If one were somehow damaged, then I would recommend replacing just that O2 sensor.
I don't have any empirical evidence to back up this theory but that is the reason that I recommended to this guy that he should replace them both at the same time.
-B-