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.