Here is the steps for Ubuntu Server 8.04.1 and PHP5. Like Djamu said it will install a GD pre-compiled working version. It is a complete bundled (forked) GD libraries:
1. If not already done removing your current GD package and its configurations.
sudo apt-get --purge remove
2. Adding 2 lines to your file /etc/apt/sources.lst
3. Updating your current apt-get list
4. Installing working GD package.
apt-get install php5-gd
It will complain about non-authenticated sources, just ignore, it will also update some additional php libs.
When prompt select keep_current modified php.ini
5. Restarting Apache