I always compile my new kernels manually and install them manually. I don't like package managers
But, I read somewhere that Debian only installs new kernels on "apt-get upgrade" to /boot/, but it doesn't activate them. Take a look at /boot/ and /etc/lilo.conf. Then make a new entry to lilo.conf of similar vmlinuz-[kernel-version] than the others. Make the new kernel the default, so it will start the new kernel in reboot.
You're probably doing this the first time, and you're doing it remote. If something goes bad and the server doesn't reboot, there's nothing you can do. Some ISPs have very good rescue systems so you can reboot to the rescue system, fix the lilo.conf to reboot the old kernel and restart. Some ISPs have not-so-good rescue systems and you'll have to do all sorts of tricks to revert to your old kernel (usually problems are that devices at /dev/ are not in the same order, or lilo writes the boot loader to wrong place, etc...). Grub (alternative boot loader) is bit more difficult to configure, but it's better because it can read config file on-load and doesn't mix harddrive devices because it looks at their unique IDs instead of the primary/secondary and/or cable order.
I recommend you don't start to do this by yourself. You risk making your system unbootable and you could end up having to pay-by-hour for your ISP to get the old kernel reverted. At least make sure you've got good plan what you're going to do when your server doesn't reboot. I speak of experience