I finally had time to site down and actually analyze what happened to my box. It was certainly compromised by a script kiddie, but I'm not 100% sure if it was an inside job or not. In any event, I stored off the broken image and re-imaged the machine back to my "last known good" configuration.
I subsequently added the account that I thought was used for the attack setting the password back to what it was when the machine was originally compromised, but limited login to the rssh shell. This has been running for almost a week with no problems now. I've had a couple of sniffs of folks trying to connect to my machine as root, but no solid hits.
Some initial observations:
First the default install of Ubuntu Server on rackspace's cloud accounts enables root login via ssh. This is very strange now that I think about it. Ubuntu, by default disallows this (for very good reasons), and I think rackspace should seriously consider a change to their default build.
Second, the root password is emailed to customers. Again, really bad idea, not only is email really insecure, but there is certainly a more convenient method. Only display the password on the ssl admin console and push the responsibility of maintaining a good password policy to the customer.
Third, Not only should the root account ssh login be disabled by default, but users should have an option to have the initial boot of the system start the network interfaces disabled. I really would like to build a secure image, but it's nearly impossible when the server is started with network interfaces enabled.
So at this point, Rackspace's cloud accounts are exposing their customers to multiple attack vectors with zero chance of allowing the customer to secure their machine BEFORE an attacker has already breached their system. These are actually pretty minor changes to policy and configuration that have serious implications for security.