First, you need to understand that Buddhist texts operate on two levels of description: the conventional truth and the ultimate truththe conventional truth and the ultimate truth. The contradiction disappears when you realise that anatta (the non-existence of self) is an ultimate truth, while the rebirth is a conventional truth.
In other words, Buddhists believe that people linked by a chain of rebirths may be said to be "the same", by the same convention as when a 40-year-old person is said to be "the same" as an 20-years-old person he evolved from. This convention has nothing to do with the fact that there is no indivisible and constant "I", and that the aggregates that make up the conventional "I" are in constant flux.