Estou usando o xubuntu 16.04 LTS e estava com o mesmo erro. Tentei fazer isso e trabalhei:
sudo /usr/lib/virtualbox/vboxdrv.sh setup
deveria dizer isto:
Stopping VirtualBox kernel modules ...done. Recompiling VirtualBox kernel modules ...done. Starting VirtualBox kernel modules ...done.
e então você pode verificar se isso funcionou usando:
sudo /usr/lib/virtualbox/vboxdrv.sh status
tente executar novamente o genymotion :) Espero que ajude!