I had the same problem and I thought it could be related with virtualization hardware settings since few tips that I found (google) suggested to enable Intel Virtual Technology in BIOS, but I didn't try that.
In further investigation, I've checked that the issue could be related to PAE/NX option in Processor settings, just need to enable it.
steps: Select VM > Settings > System > Processor tab > Extended Features: Enable PAE/NX.
Surprisingly, in my virtual box settings this option was already enabled, so what I did:
- I've disable PAE/NX checkbox
- tried to start the VM and got an error
- got back to the settings to enable PAE/NX feature
- tried to start the VM once again
After that, it worked, please try with the steps above.