I have a 1996 Legacy that is overheating. After looking over the car, it only overheats under load after driving for about 5 min after it warms up. It happened before and i noticed the coolant had a brownish hue to it and the catch tank was dirty as all hell. After flushing the system and replacing the cap and thermostat it started overheating again a month or so later. Now it coolant is very brown and the catch tank is filthy again. the car only overheats under load. I also have a check engine light that comes on every so often. It will be on for a week, then turn off for a few days, then turn back on again. And when i got the light checked i got an P0440 code. If it helps any, it has the 2.5L motor in it.
The brownish color of the coolant means that oil and coolant circuits mix. This is most probably a symptom of a leaking head gasket. If this is the case you should have it repaired asap, as it typically affects not only heating but also lubrication, and this can seriously damage the engine over time.
Simply overheating would not contaminate the coolant. As answered above, it could be contaminated with engine oil, or even transmission fluid if the radiator has an integrated transmission heat exchanger.
You could also have combustion gases leaking into a coolant passage, either through a crack or a failed head gasket. I'd suggest a compression test to see if you have a cylinder low. Alternately, there are combustion leak test kits. Google that term to find them, and they are about $50.