When you changed the fluid did you completely drain and flush the block?, if not there could be a blockage (original Apple fluid can crystalize) preventing the fluid flowing properly. Make a 50/50 water and white vinegar solution and run this through the block, it will help remove any blockages.
Bleeding the air can be difficult but you have to be sure you get it all out. You also mention in your post that the pump is not working well, this is a problem as fluid will not be forced through the block causing overheating. You say there were no leaks, many people have thought this only to find leaks at the O-rings, to check you need to remove the processors form the LCS, you may well find 'white rice' crystals which is a sure sign of leakage and you will need new O-rings.
To do this repair properly you will need some, or all, of the parts I reference earlier in the post. It seems obvious but strip the unit down, replace what is damaged and re-assemble. These units were never designed to be serviced so we have to find our own solutions. Feel free to ask more questions, but take a look at this site for more info.
http://www.xlr8yourmac.com/systems/G5_CoolantLeak_Repair/G5_CoolantLeak_Repair_p 1.html