On both my straight-up-Debian system as well as my Ubuntu system I can't find kernel 2.4.31 anywhere...But that might be the fact that I'm running unstable/Breezy depending on which system you're talking about.
Try running apt-cache search headers | grep 31 -- or some variant of that on the grep side of things -- to find the correct linux-headers-* package to install.