How did you take him off the student worker list? It seems that you made his record inactive, which explains the message he's getting. One solution to this is to edit his record (in the Modify Staff screen) and change his sign-in ID and save (e.g. change the first 3 digits to 000).
I did make him inactive, because I do not want his name to appear as a tutor when students sign out from tutoring. Is there another way to keep him off the tutor list? Like removing his assigned classes? If I do that though, I thought it might affect data from past semesters. Like if I look back at Fall 2009, will it still show that this student assisted with Math 090 if that class is no longer assigned to him as a student employee?