Conjectures that have been disproved with extremely large counterexamples? I just came back from my Number Theory course, and during the lecture there was mention of the Collatz Conjecture.
I'm sure that everyone here is familiar with it; it describes an operation on a natural number – $n/2$ if it is even, $3n+1$ if it is odd.
The conjecture states that if this operation is repeated, all numbers will eventually wind up at $1$ (or rather, in an infinite loop of $1-4-2-1-4-2-1$).
I fired up Python and ran a quick test on this for all numbers up to $5.76 \times 10^{18}$ (using the powers of cloud computing and dynamic programming magic).  Which is millions of millions of millions. And all of them eventually ended up at $1$.
Surely I am close to testing every natural number? How many natural numbers could there be?  Surely not much more than millions of millions of millions. (I kid.)
I explained this to my friend, who told me, "Why would numbers suddenly get different at a certain point?  Wouldn't they all be expected to behave the same?"
To which I said, "No, you are wrong!  In fact, I am sure there are many conjectures which have been disproved by counterexamples that are extremely large!"
And he said, "It is my conjecture that there are none! (and if any, they are rare)".
Please help me, smart math people.  Can you provide a counterexample to his conjecture?  Perhaps, more convincingly, several?  I've only managed to find one! (Polya's conjecture). One, out of the many thousands (I presume) of conjectures. It's also one that is hard to explain the finer points to the layman. Are there any more famous or accessible examples?

Another class of examples arise from diophantine equations with huge minimal solutions. Thus the conjecture that such an equation is unsolvable in integers has only huge counterexamples. Well-known examples arise from Pell equations, e.g. the smallest solution to the classic Archimedes Cattle problem has 206545 decimal digits, namely 77602714 ... 55081800.
