O local ~/.local/share/icons
ainda é uma coisa válida em 16.04, geralmente não é necessário e, portanto, alguém decidiu não criá-lo por padrão. Se você quiser usar este diretório, basta criá-lo.
No entanto, os arquivos .desktop
específicos do usuário precisam ir para ~/.local/share/applications
para ter um efeito.