Also für normal sollte es mit NAT meistens funktionieren. Sind die GuestAdditions installiert? Hast du mal einen anderen Adaptertyp ausprobiert?
Sollte das nichts bringen, wäre meine nächste Empfehlung auch die Netzwerkbrücke gewesen. Hier natürlich dann den Adapter auswählen, welcher als Gateway fungieren soll.
Sollte auch das nichts bringen, kannst du noch versuchen, den Netzwerktyp auf Host-only umzustellen (hier den Virtualbox-Adapter auswählen) und dann im Netzwerk- und Freigabecenter manuell ein gemeinsames Netzwerk einzurichten. Dafür machst du einen Rechtsklick auf den Gateway-Adapter, wählst dann Einstellungen, wechselst auf den Tab "Freigabe", aktivierst das Kästchen und wählst dann den Virtualbox-Adapter aus. Das zweite Kästchen kannst du deaktiviert lassen.
Spätestens jetzt solltest du eine Internetverbindung bekommen, eine Verbindung mit anderen VMs ist so allerdings nicht möglich (also klar, theoretisch schon, ist aber ein bisschen umfangreicher einzurichten).