I had the same issue for my old laptop (HP nw8000) on Ubuntu 10.10, I fixed it by:

1. Open Terminal
2. Type in: alsamixer
3. Use right/left arrow key and select <headphon> (aka Headphone Jack Sense)
4. Press m on your keyboard to modify (from default OFF to ON)
5. Press Esc (escape key) to quit the alsamixer app

and woalaa... it magically and immediately senses my plugged-in headphone and routes the sound appropriately.

Note: for my case, other posted solutions (like updating ALSA drivers, editing the 'alsa-base' file, etc) killed my audio driver completely, and i had to do a reinstall of Ubuntu 10.10 to get them back.

Reference: http://ubuntuforums.org/showthread.php?t=900898