Today I got an email from the nice sysadmins at Rimuhosting telling me that my VPS had been hacked, and the hacker installed a root level exploit.
I'd like to thank the Rimuhosting sysadmins for there quick response. They identified excessive network traffic coming from my host, investigated, shutdown my VPS and then sent me an email. The email included all my options. I choose to recover from a backup, then change all my passwords. That worked, and got me back up an running in under 15 minutes.
Thanks Rimuhosting for the help. If you need a VPS check out Rimuhosting.