I ordered my second NodeDeploy VPS today (PS: They're awesome) and I wanted to reinstall it to run Ubuntu 12.04 instead of Debian 6.0 that it came with. I'd done it before but I couldn't find how to do it in the client's control panel.
As it turns out, you can't do it in there, you need to be in the VM control panel. To find your username + password, log in to the clients area and click on the icon on the right hand side of the server you want to log into.
Scroll to bottom of this screen and look for "Login Details". The box will contain a username and password. Use these to log in to the VM control panel.
Click on the VPS you want to manage, scroll to the bottom of the screen. In the "Controls" box, select the General tab and then click on "Reinstall" (It's the white button). Choose your distribution and off you go - give it 10 minutes or so to reinstall before trying to log in. If you can't log in, use the "root password" tab in the VPS control panel to reset your password and log in using that. With a bit of luck, you should now be logged in to your new OS.