How can I work out why my headless VirtualBox VM is not booting?

Question

I have an Ubuntu Server, upon which I am trying to run a headless VM (Ubuntu Server as the guest OS) with Virtualbox. The machine apparently starts up but I cannot ssh into it (though it should be running an ssh server). Normally I'd use VRDP to see the screen output, but remote desktop is not working.

So, I have two questions:

1. How can I troubleshoot a VM without RDP? I've tried looking for a VM log somewhere, to no avail.
2. What else can I do to get RDP working again? I've ensured that RDP is enabled, along with the Virtualbox extensions. I've tried several Windows machines with the built-in RDP-client, but none of them are able to connect. In my host machine, I can see that virtualbox has bound the port correctly and have even used tcpflow to verify that there is traffic at the port when I connect (I've included that below in case it's useful). The VBox RDP server appears to be consistently responding with 4 (and nothing else) twice, though I'm not sure if this is somehow part of normal RDP or an indication of some problem!

Everything was working without issue prior to the 15.04 update; but since I have updated both the VM image and the host OS at approximately the same time, I can't tell which is causing the issue.

---

Starting the VM appears to work:

$ vboxheadless -s "ubuntu-server"

Oracle VM VirtualBox Headless Interface 4.3.26_Ubuntu
(C) 2008-2015 Oracle Corporation
All rights reserved.

VRDE server is listening on port 5001.

And there's the communication that occurs when I initiate an RDP session, though it's not much:

# tcpflow -i any -C -J port 5001

tcpflow: listening on any
72$-tGc
4
72$-tGc
4
e0"0 0Q|HDuca:M'ENIGMA-BOMBE3dea5e18-0c19-4eb3-9839-0ec237bDdd8rdpdrrdpsndcliprdrdrdynvc