I created a new user and found that sound works correctly with the new user. That means that something was wrong in user configs. I found some configs and it looks like the problem is solved. The files were not in text format and I have no idea what that format is.
I removed all files from ~/.config/pulse/ and rebooted. Now it works OK.
I also removed all files from /root/.config/pulse/ to fix 100% volume on login screen.
I think they've changed format of some config files in the new version of pulseaudio. The config from 14.04 confused pulseaudio in some way.
I saw some bug reports about this issue. It may happen when you replace Ubuntu versions with the same /home.
Update: This looks like a distro upgrading bug. I upgraded 14.04 to 16.04 on another computer, and there was the same issue.
cookie file needs to be removed in ~/.config/pulse/ after an upgrade.