I had similar problems myself when upgrading to the 2.6 kernel. Two things to try:
1.) you'll have to reinstall the kernel. This will involve doing an apt-get remove <kernel name> and then doing apt-get install <kernel name>. Make sure you run whatever boot-loader you have installed, either grub or lilo, BEFORE you reboot into the new kernel-that's what got me the first time, I forgot to run lilo after installing the new kernel.
2.) if that doesn't work, try installing the 386 version of the new kernel. It's almost as fast as the 686 version, and seems a bit more compatible and stable.