does this vehicle have a procedure to remove any air pockets from the cooling system after doing such work?
a before and after problem sounds to me like a radiator issue, so i might suggest you have that flow tested.
water pumps on these motors rarely are cause for overheat issues because they spin all the time and its very unlikely the impeller is so bad it wont pump water.
another possibility might be ATF fluid being too hot in the radiator. perhaps sample the ATF and send to lab if radiator checks out ok.
running way too lean can cause heat problems, but i would expect CEL to pop on this one.