Dê uma olhada nas Notas de versão . Ele diz exatamente o que vai acontecer, e IMHO, é um passo na direção certa, não um problema.
O driver fglrx agora está obsoleto em 16.04 e recomendamos suas alternativas de código aberto (radeon e amdgpu). A AMD dedicou muito trabalho aos drivers e fizemos o backport do código do kernel do Linux 4.5 para fornecer uma experiência melhor.
Ao atualizar para o Ubuntu 16.04 a partir de uma versão anterior, tanto o driver fglrx quanto o xorg.conf serão removidos, para que o sistema seja configurado para usar o driver amdgpu ou o driver radeon (dependendo do hardware disponível).
Mais informações estão disponíveis no link