Eu tinha o wicd e o Networkmanager instalados. A desinstalação do wicd, juntamente com a implementação das soluções da questão relacionada acima, resolveu meu problema.
Parece que tanto o wicd quanto as rotinas de gerenciamento de rede do gnome tentam se conectar ao meu wifi quando eu estou desconectado. As rotinas do wicd são geralmente mais rápidas e do que as do gnome não reconhecem que estou online, o que leva à confusão em outros programas, como a evolução.