What is the difference between classification and prediction?

Gregory Piatetsky-Shapiro answers:
The decision tree is a classification model, applied to existing data. If you apply it to new data, for which the class is unknown, you also get a prediction of the class.

The assumption is that the new data comes from the similar distribution as the data you used to build your decision tree. In many cases this is a correct assumption and that is why you can use the decision tree for building a predictive model.

When Classification and Prediction are not the same?

Gregory Piatetsky-Shapiro answers:
It is a matter of definition. If you are trying to classify existing data, e.g. group patients based on their known medical data and treatment outcome, I would call it a classification. If you use a classification model to predict the treatment outcome for a new patient, it would be a prediction.

gabrielac adds
In the book "Data Mining Concepts and Techniques", Han and Kamber's view is that predicting class labels is classification, and predicting values (e.g. using regression techniques) is prediction.

Other people prefer to use "estimation" for predicting continuous values.