Eu tenho exatamente o mesmo problema para o Borderlands The Pre-Sequel com uma placa gráfica da Nvidia, o mesmo sistema operacional.
O problema realmente ocorre apenas no modo de tela cheia, eu defino o jogo no modo de janela e agora tudo bem.
Para evitar a reinicialização do computador toda vez, basta conectar-se a outra sessão virtual (Ctrl + Alt + F1), interromper o processo e voltar à sessão virtual executando o servidor X (Ctrl + Alt + F7 para mim).