To be honest with you, it sounds like your server got hacked and it's not compromised.
If I were you, I would cut my losses and reload from scratch, that's the best way to go (if you can of course).
Otherwise you don't know what the intruder left behind in the order of some type of backdoor, trojan, etc...
Also, one other thing you want to look for is known issues with your web apps that you can fix with patches. I assume you're running a web server. Most likely that's how you got it. Someone managed to drop a shell in your box and eventually got your root password.
Remember, always use alphanumeric, long passwords. It is always a good idea to use at least 1 or 2 upper case characters in it. You don't have to change it very often if it's strong enough.
The way linux passwords are encrypted, they cannot be decrypted but they can be brute-forced, thus if you use a really strong password the chances are slim to none.
Chances are your logs are gone because that's the least the intruder would do - delete logs to cover their tracks.
You may also want to look at your router's logs (during that time frame) and see what its logs may revel to you about the potential intruder. Remember, getting his/her IP address won't do you any good. Most attacks come from several chained proxies so forget about finding the original IP of the attacker.
I don't want to scare you or anything, this may not be the case, maybe you had to deal with a disgruntle employee or whatever, however I would take no chances.
One last thing to keep in mind is that if this is not the only machine you own, but seems to be the only machine affected by this, you may want to take a closer look at the rest (if this applies to you).
Let me know how you make out or if you need help.