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.