I run Ubuntu 9.10 x64 using PulseAudio (the Ubuntu 9.10 default) on my primary computer for everything except gaming. About kernel
2.6.31-17 I noticed my sound stopped working. The volume controls still seemed to work but, alas, no audio. I tried everything I could think of or find online. As it turned out there was nothing wrong with PulseAudio. The problem was that my modem was grabbing the sound device before PulseAudio could (which also accounted for why every ~25th boot my sound would work fine).
Below are the simple steps I took to fix my issue.
sudo fuser -v /dev/dsp* /dev/snd/* /dev/seq*
sudo killall slmodemd
sudo killall pulseaudio
fuser is only used to confirm the modem is the issue while
pulseaudio will restart after killed, thus properly grabbing the sound device.
Since I not using my modem these steps worked for me. Obviously this would cause a problem for you if you were using your modem. If that is the case check out one of the other proposed solutions and see if one of those works for you.