I had the same problem (VirtualBox 4.1.10, Host Ubuntu 11.10, Guest Ubuntu 11.10). Here's how I fixed it:
Set two network interfaces for the VM. The first one should be NAT and the second should be Host-Only. If you can't add a host-only connection, make sure you've set one up in Preferences -> Network.
In the Guest OS (Ubuntu for me), edit /etc/network/interfaces, adding the following on the end:
auto eth1 # this refers to the Host-only network interface
iface eth1 inet static
address 192.168.56.10 # Arbitrary IP address
netmask 255.255.255.0
and reboot. And that's it. Don't modify anything for eth0, since we need that getting it's settings automatically via DHCP to access the internet. eth1 lets the host and guest communicate with eachother.