A quick search brings up hits that all indicate you need to enable virtualization in your BIOS, and then this problem will be resolved. However, I hadn’t changed the BIOS and this had worked before, so … was that really the explanation? I rebooted and checked the BIOS, and sure enough virtualization was enabled, so it was something else.
Strangely enough, it turns out the issue ended up being that VirtualBox for whatever reason does not detect CPU virtualization technology correctly if a feature called Hyper-V is turned on in Windows. At some point, I imagine I must have enabled this feature for whatever reason.
You can get rid of Hyper-V in Windows 8/8.1 by going to Control Panel -> Programs -> Programs and Features -> Turn Windows features on or off and un-checking the top level Hyper-V checkbox shown in the screenshot above. You will need to click OK a few times and likely reboot, but after that, your 64-bit VirtualBox virtual machines should be back to running good as new.
It would be really nice if this is a bug if the Oracle VirtualBox team would fix the issue, or if it is a known limitation, to at least make the error message a little more accurate to indicate what the problem really is.