VT-x/AMD-V hardware acceleration not operational with VirtualBox
Self Answer:
In the BIOS (In my machine, hold F1 during boot-up.) I enabled CPU > Intel Virtualization Technology. Then it worked.
I also stumbled into this issue on a Lenovo T420s. I had virtualization enabled and TXT disabled, but still got this error. The Intel Hardware Accelerated Execution Manager for Android was locking the virtualization subsystem and wouldn't let either virtualbox or Virtual PC use it. Uninstall or disable it, and you should be fine.
More info: https://forums.virtualbox.org/viewtopic.php?f=8&t=49479