SilasBarta has half the answer, which is that public punishment of criminal A is excellent for deterring law-abiding citizen B from committing crimes.

The second half of the answer is that most people believe in justice. Justice makes little sense from a Utililitarian perspective (except that public justice deters others), but it is a commonly held belief that bad deeds actually do deserve punishment regardless of the utilitarian function involved. The belief exists not only in most societies, but also among most intelligent animals (particularly primates). Now, a utilitarian may want to discard this evolutionary baggage, but to do so will be very politically difficult.