Entre em configurações, itens de inicialização. Adicione uma entrada com o seguinte comando:
gksu "service network-manager start"
Você também pode usar visudo para adicionar uma entrada NOPASSWD para este comando, para que você não precise fornecer uma senha.