When does it get hot? Sitting still? On the highway at speed?
Make sure the fan if blowing back through the radiator and not blowing from the engine side. The fan will run both directions depending on how's it's wired.

If your using an electric fan how are you using a fan clutch?

As far as the engine being new and tight: Thats BS. If thats the case they didn't build it right. A newly rebuilt engine should have all the clearances right when they rebuild it.