Let me say this, you will have to have a lot of air in the cooling system, for your car to overheat.
Allowing for the fact, that unless you can drain both the block, the radiator, and the heating system, you may not get all the old coolent out, HOW MUCH coolent did you have to put in, compared with the systems total capacity.
Bleeding the air out, can sometimes be a long time project, because there are so many pockets, that air can be trapped in.
The sign that all the air is gone, is if your car has one, the coolent tank level stops dropping.
If you do not have a tank, then the level in the radiator, stops dropping. To get all the air out quickly, you need to ensure that the heating system is full on. Make sure you remove cap, only when the engine is cool.
I suspect you may have a crook thermostat.
You can check that, by removing it, and putting it in a cooking pot, but you must suspend it on a piece of string, WHERE IT DOES NOT touch the sides or bottom.
When the thermostat is cold, it should be closed, and as the water temperature comes up, it should slowly open and at the temperature that should be stamped on it, the thermostat should be fully open.
Do not drill or remove the centre of the thermostat, because your car will run so cold, that performance will drop off, and premature engine wear will take place.
Inspect the thermostat housing or cover, for rust as this item often can fail, just at the wrong time. It is cheap, as is the thermostat, so when in doubt chuck them out.
Also is the ignition timing correct, too far retarded and that can cause overheat.
The radiator, have you had it cleaned, it may be even though the coolent may not indicate, be partly blocked with muck over the years.
When you are running the engine, and it gets to full heat, check that the hoses are not being crushed and restricting the water flow.
You can run through these problems one by one, rather than change and do everything, which may not be required.
Let me know if I can be of more help.
Col Tigwell Downunder