Bem, aparentemente, a atualização para o Ubuntu 13.04 resolveu tudo desde que, mesmo depois das sugestões de @Meer Borg, eu consegui menos botas aleatórias do que antes.
Até agora eu estive no 13.04 por 2 dias e ele funciona perfeitamente toda vez:)