I had this problem - after playing around with it, I've figured out how to fix it, although I'm still not sure what's wrong with it.
First find the card and device you want and manually export the PULSE_SINK variable:
$> aplay -l
**** List of PLAYBACK Hardware Devices **** card 0: PCH [HDA Intel PCH], device 0: ALC269VC Analog [ALC269VC Analog] Subdevices: 1/1
Subdevice #0: subdevice #0 card 0: PCH [HDA Intel PCH], device 3: HDMI
0 [HDMI 0] Subdevices: 0/1 Subdevice #0: subdevice #0
Now you should be able to start pulse.
$> pulseaudio --start
If not, check /etc/pulse for broken symbolic links and
rm -rf ~/.config/pulse.
Thereafter make the default to where you want, check
After you find which output you want then, make it the default:
$> pacmd set-card-profile 0 output:hdmi-stereo
Works for me, on Ubuntu 16.04.