D'oh, that really sucks, glad you found it.
While I haven't had any experience with this keylogger a quick Google search brings up loads of info. I'd check this page out and follow the steps to be sure the system is 100% clean.
Remove Spyware
Most keyloggers send info out over email, so your firewalls probably didn't stop much. And about changing passwords, yes, do it soon and do it from a computer you believe to be clean.
Good Luck!