This is a well-known and well-documented example: the first proof of the Alternating Sign Matrix theorem was a complicated, inductive "manipulation of generating function"-style argument by Zeilberger; shortly thereafter Kuperberg gave a shorter proof based on a connection to the six-vertex model of statistical mechanics and the Yang-Baxter equation. The history of the Alternating Sign Matrix conjecture is beautifully told in the book Proofs and Confirmations by Bressoud.