Maybe this will save someone else the multi-hour troubleshooting
session I went through.
If you have one of the new Macs (2011), are trying to use vagrant, and
it is unusably slow: this issue is with VirtualBox and not vagrant.
VirtualBox does not work well with the new processors and/or 64-bit
kernel. There is a lot more detail in the ticket linked below.
You can read more here:
http://www.virtualbox.org/ticket/8474
As a workaround you can boot into a 32-bit kernel:
http://support.apple.com/kb/HT3773
Kyle