I had this exact problem, and had also tried all the steps you mentioned. In my case, it turned out to be a permissions issue. For some reason, my user account wasn't in the "audio" group, so I didn't have the correct permissions to (I think) /dev/dsp.
Here's the steps I used to fix it:
Open /etc/group in an editor as root:
tim@nightcrawler$ sudo vim /etc/group
Then find the line that reads something like
And change it so it reads something like
(where tim is your username instead)
Then I logout/login again.
Hope this also fixes your problem