Nothing - neither the fly nor the train - is prefectly rigid. When the fly hits the train, it microscopically deforms the surface of the train - even if only temporarily. If one wanted to calcualte the momentum of the train (the train *alone*, not including the fly) before- and just after- impact, one would see that the momentum of the train was infinitesimally smaller. Because a very small piece of the train has slowed down, the train's *average* speed is less.
This puzzle is only a paradox is a universe where objects are perfectly rigid.