Em versões mais recentes do Ununtu, o pacote é conhecido como linux-firmware-nonfree. Você também pode precisar reconstruir o índice do pacote. Por favor, tente:
sudo apt-get update
sudo apt-get install linux-firmware-nonfree
Desanexe a ethernet, reinicie e você deve estar tudo pronto.