Eu estava enfrentando o mesmo problema de não me conectar à internet com meu Genymotion instalado no Ubuntu 15.04 e o dispositivo virtual que eu estava usando era o Google Nexus 5-5.1.0-API 22-1080 * 1920. Minha conexão de internet regular através da máquina desktop é através de uma banda larga conectada por cabo.
E na caixa virtual > Configurações > Rede > Adaptador 2 > foi apenas a configuração padrão, que é "Anexado a" foi "NAT" e "Conectado por cabo" foi verificado.
Então, depois de lançar o dispositivo virtual Google Nexus 5-5.1.0-API 22-1080 * 1920 > Eu acabei de entrar em Configurações > Wi-Fi > Deixe-o selecionar o IP automaticamente > Depois disso, basta clicar em Concluído > e agora estou conectado à internet