We need an addition command-line tool called qemu.
sudo aptitude install qemu
You’ll new be able to convert a .vmdk (VMware image) to a .bin format, which can then be converted to a Virtualbox native .vdi format.
qemu-img convert /path/to/original.vmdk converted.bin
You’ll then need to use the VBoxManage utility that comes with Virtualbox to convert the .bin to a native .vdi format:
VBoxManage convertdd converted.bin converted.vdi
You can now create your new Virtualbox machine profile, using this new .vdi file as your disk image.