The first two things that come to my mind are actually the dual of what you asked for, namely conjectures where the counterexample did not come first, and the search for an explicit counterexample led to interesting developments.
Brosnan and Belkale disproved a conjecture of Kontsevich about polynomially countable graphs, but their argument did not lead to a specific counterexample. An explicit counterexample was provided by Dzmitry Doryn.
That $\pi(x) > \mathrm{li}(x)$ for all $x$ was disproved by Littlewood, but without giving an explicit counterexample. I believe that there is still no explicit counterexample, but the search for one has inspired some interesting work.