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?

A case where you can "dial in" a large counterexample involves this theorem:
"A natural number is square if and only if it is a $p$-adic square for all primes $p$."
A $p$-adic square is a number $n$ for which $x^2\equiv n\bmod p^k$ has a solution for any positive $k$.
If we include all primes $p$ we have no counterexamples, but suppose we are computationally testing for squares and we have only space and time to include finitely many primes.  How high we can go before we get a non-square number that slips through the sieve depends on how many primes we include in our test.
With $p=2$ as the only prime base, the first non-square we miss is $17$.  Putting $p=3$ in addition to $p=2$ raises that threshold to $73$.  Using $2,3,5,7$ gives $1009$ as the first "false positive".  The numbers appear to be growing fast enough to make the first counterexample large with a fairly modest number of primes.  See http://oeis.org/A002189 for more details.
