Eu tive o mesmo problema hoje (2016-08-29). Não está claro o que causou, já que não atualizei nada nos últimos 4 dias.
A reinicialização não ajudou.
Observação chave: xev
não estava mostrando nenhum evento vindo do mouse ao clicar o botão do meio do mouse (roda de rolagem) dentro do xev
pequeno quadrado. Isso indicou algum problema de driver de baixo nível em oposição a um problema de configuração do aplicativo.
A seleção de mouse estava funcionando bem: clicar em Shift + Inserir ou executar xsel
de um terminal estavam ambos colando a seleção atual.
Apenas a colagem pelo botão do meio do mouse não funcionou. O problema afetou todos os aplicativos, incluindo o firefox e os terminais.
Por fim, isso resolveu isso para mim.
sudo dpkg-reconfigure xorg