A linha
modprobe: ERROR: could not insert 'nvidia_352': Required key not available
teve a pista certa. Em suma, o novo kernel parece não carregar módulos de terceiros não assinados (o driver Nvidia no meu caso). A desativação da inicialização segura nas configurações UEFI (BIOS) resolveu o problema. Essa resposta me ajudou a desativar o Secure Boot para minha placa ASUS um pouco mais rápido.
Esta resposta tem um bom histórico, uma possível solução alternativa, e menciona que o problema começa com o kernel 4.4.0-20 . No meu caso (Ubuntu 14.04), o kernel que causou problemas é o 3.16.0-77.