[CentOS] Up2Date and yum failing

I have 2 new servers built from 4.3 isos. I want to update them but 
cannot do that because of update issues:

Up2date fails because of a several dependency issues.
yum update fails because of a problem with the au mirrors. yum can find 
the mirrors but not the headers.

Cheers