There is a version of linux I've used to reset windows machines, but I can't remember the name of it, it had a neat little text wizard that walked you through the process, and it worked with linux machines too, I'm not at home and can't remember the name of it right now.....but I did find these....
http://linux.suramya.com/tutorials/ResetPassword/
http://achmadz.blogspot.com/2007/11/...x-live-cd.html
After resetting your root password, I'd reset any and all user passwords too.....just in case he left himself a way back in...
Oh, I have no idea what you mean about gnome having it's own password store. I don't think it does. I think it's more likely that you didn't have the partition mounted rw or you forgot to chroot to the correct filesystem, or edited the wrong file. I'm not sure, but I've never heard of gnome containing the passwords on it's own, independent of /. I'd be shocked if that was the case.......
Good luck...
David
Oh, if that is a server at a business, you should not be running gnome. You shouldn't be running any gui unless there is a good reason to. Besides wasting electricity, it's another way for your system to be attacked. If you don't need it, turn it off, is a very good rule. Think about attending the next local Linux Users Group meeting, and hiring someone to set up that server for you so it's not a danger. Someone might even do it for free, but it shouldn't cost much in any event, and the local linux guru might think it's a kick to get paid, even if it's just a little bit.