There is a famous rejection, not in CS but in econ, that I know of: Milton Friedman, one of the most influential economists of the 21st century, winner of the John Bates Clark ('51) and Nobel ('76), and preeminent monetarist was fired by the econ department at the University of Wisconsin Madison for being jewish and too data driven. They did not advertise this fact at the department when I was there =P He went 90 minutes south to Chicago and it seemed to work out for him. It would be nice of UW econ apologized though, even if a bit late.