Seems like a dependency issue, which is also what is stated here: https://askubuntu.com/questions/122211/getting-error-message-when-trying-to-start-a-virtual-machine
Did you install using Synaptic? If not, I suggest uninstalling and reinstalling, both steps using Synaptic.