To make a new base VM:

1) Install your OS (only tested with Ubuntu 10.04 64-bit)
2) Setup a user with a password that you don't mind hardcoding in your Bumfile
3) Make sure that user has no-password sudo access
4) sudo apt-get install ruby1.8 ruby1.8-dev libopenssl-ruby rubygems ssh
5) sudo gem install chef
6) Delete /etc/udev/rules.d/70-persistent-net.whatever
7) Shut down VM
8) Remove all *.lck files from inside the VM's vmwarevm folder

DONE!