Abra o Software and Updates e vá para a guia "Outro Software". Você verá todos os seus ppas desmarcados e rotulados como "desativado na atualização para xenial".
Basta marcar as caixas e clicar em fechar. Ele vai querer recarregar as informações - deixe-o - e então você pode reinstalar o software.
Se você quiser se livrar da linha dizendo "desativado", você pode destacar o ppa e clicar em editar. Faça a alteração na caixa de comentários.
Isso funcionará a menos que os ppas não existam para 16.04