Oh wow. Is there any other explanation for this other than this having been exploited in the wild for almost three weeks? Or maybe someone just tried to log in over SSH to exploit some other weakness (something like predictable SSH passwords on jailbroken iOS devices), and happened to create the root user on your machine?

Did you also have sshd running, and do you know what kind of network you were using at the time?