This one frustrated me enough that I have to post the solution.
At work we run RHEL4 on our production servers but with limited licences I decided to try CentOS4 for testing. I’d been mucking around with VirtualBox and as my test hardware had died I decided to try it.
When it came to installing the Guest Additions I hit a roadblock. I followed the instructions for installing the headers:
yum install kernel-devel
…but that wasn’t working. I was still getting:
Please install the build and header files for your current Linux kernel.
The trick is to create the default symbolic link to the header files:
ln -s /usr/src/kernels/2.6.18-92.1.18.el5-i686 /usr/src/linux
Problem solved by jeffreywt on the VirtualBox Forums.