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 example: Euler's sum of powers conjecture, a generalization of Fermat's Last Theorem. It states:
If the equation $\sum_{i=1}^kx_i^n=z^n$ has a solution in positive integers, then $n \leq k$ (unless $k=1$). Fermat's Last Theorem is the $k=2$ case of this conjecture.

A counterexample for $n=5$ was found in 1966: it's
$$ 61917364224=27^5+84^5+110^5+133^5=144^5 $$ The smallest counterexample for $n=4$ was found in 1988:
$$ 31858749840007945920321 = 95800^4+217519^4+414560^4=422481^4 $$ This example used to be even more useful in the days before FLT was proved, as an answer to the question "Why do we need to prove FLT if it has been verified for thousands of numbers?" :-)

My favorite example, which I'm surprised hasn't been posted yet, is the conjecture:

$n^{17}+9 \text{ and } (n+1)^{17}+9 \text{ are relatively prime}$

The first counterexample is $n=8424432925592889329288197322308900672459420460792433$

A famous example that is not quite as large as these others is the prime race.

The conjecture states, roughly: Consider the first n primes, not counting 2 or 3. Divide them into two groups: A contains all of those primes congruent to 1 modulo 3 and B contains those primes congruent to 2 modulo 3. A will never contain more numbers than B. The smallest value of n for which this is false is 23338590792.