Acabei de atualizar o Sublime Text para a versão mais recente no Ubuntu 16.04LTS.
Eu posso ver um novo ícone para o programa em
usr/share/applications/
No entanto, este ícone não é usado no meu dock de inicialização do Ubuntu.
Eu olhei o atalho no gedit e o ícone está definido como 'sublime-text'
Eu também reiniciei desde a atualização.
Eu sei que provavelmente posso corrigi-lo editando o caminho do ícone no arquivo de atalho, mas há outra maneira de fazê-lo.
Eu tive o mesmo problema. Foi causado por uma configuração local (personalizada) do ícone da área de trabalho. Eu devo ter tido uma necessidade para isso no passado.
Ele foi armazenado em ~/.local/share/applications/sublime_text.desktop (o nome do arquivo pode ser diferente para você). Renomá-lo para sublime_text.old-desktop fez o novo ícone aparecer.