[Black Tiger]

Thanks, Tiger, I am running Cent OS 5, so it's as simple as ssh-ing in as root and
yum install gd

Yes it is. So don't do a "yum install php-gd" because Centos won't understand this.
In Centos 5 it's just as I said.

yum install gd
or
yum install php-gd

nothing more. You can do a service httpd restart after that or /etc/rc.d/init.d/httpd restart but normally that is not even necessary.

Maybe I need to update it?
for Red Hat Enterprise Linux or CentOS:
up2date php-gd

This is not correct for Centos. The up2date php-gd is for RedHat. And Centos is Redhat based, but Centos does not work with up2date but with yum, so just do what I said and you will be fine.

Trust me, I've got my own hosting firm so I know how Centos is working.

I just see this:

Excluding Packages in global exclude list

Check your yum.conf for which packages are excluded, because it can be that php* is excluded.

If you have a control panel like DirectAdmin or Cpanel, you can better not do it via yum.
On Cpanel you can use easyapache.