Bridging a network connection with VBox guests:
-----------------------------------------------

dnsmasq-base has to be installed: sudo apt-get install dnsmasq-base

remove dnsmasq as it's conflicting with NetworkManager: sudo apt-get remove dnsmasq

restart (if any) NetworkManager: sudo /etc/init.d/network-manager restart

Add a new wireless network with NetworkManager (left-click on NetworkManager icon, then select "Create New Wireless Network")

Call the new network "UbuntuAdhoc" (note: if you choose another name you will have to turn on connection sharing later by editing the network you just created!)

Set encryption to "WEP40..." (note: you may have to experiment here according to what type of encryption with ad-hoc the phone/other laptop/pc supports, wpa is not supported)

NetworkManager now should connect to itself (which means it creates the ad-hoc wireless network and routes any internet traffic to your wired network interface). Now connect with the client(s) and you should have a working internet connection.