When you put in the new rad did you bleed the coolant thoroughly?
Is the rest of the coolant system still original? Make sure you check your thermostat and thermostat housing, water pump, and coolant expansion tank. Its possible that your thermostat has failed, or your water pump has failed. Pre 97 E36's had plastic impeller water pumps that were prone to failure.