Engraçado, /Varjão/, na instalação que tenho aqui da versão 16.04 continua absolutamente igual ao que era.
Se clicar no Dash, que é o primeiro ícone da barra móvel (rolante) de ícones à esquerda, irá abrir a lente de pesquisa.
Se nessa caixa digitar "atua" (obviamente sem as aspas), nem precisa digitar complelo "atualiza", basta "atua", irá imediatamente aparecer aquele tradicional ícone que você menciona, um A envolto em setas circulares do "Atualizador de Programas", bastando clicar para executar.
Além disso, também como sempre foi, quando há atualizações lá pelas tantas ele aparece automaticamente na barra de ícones oferecendo as atualizações, não vi nenhuma mudança nisso na forma gráfica.
De toda forma, se quiser testar se o procedimento de atualização, em si, está funcionando, abra uma janela de terminal (teclas Ctrl Alt T acionadas simultaneamente) e faça:
sudo apt update
sudo apt upgrade
Verifique se executa normalmente.