After wading through tens of googly results, I came across this page on the virtualbox forums which is not exactly my issue, but it does point out that an incorrect "Version" in the general tab settings can cause VirtualBox to throw this error.
Checking the settings I see it's set to Type: Other and Version: Other/Unknown
Changing these to Type: Linux and Version: Linux 2.6 / 3.x allowed the VM to boot.