What is the importance of the Collatz conjecture?
Most of the answers so far have been along the general lines of 'Why hard problems are important', rather than 'Why the Collatz conjecture is important'; I will try to address the latter.
I think the basic question being touched on is:
In what ways does the prime factorization of $a$ affect the prime factorization of $a+1$?
Of course, one can always multiply out the prime factorization, add one, and then factor again, but this throws away the information of the prime factorization of $a$. Note that this question is also meaningful in other UFDs, like $\mathbb{C}[x]$.
It seems very hard to come up with answers to this question that don't fall under the heading of 'immediate', such as distinct primes in each factorization. This seems to be in part because a small change in the prime factorization for $a$ (multiplication by a prime, say) can have a huge change in the prime factorization for $a+1$ (totally distinct prime support perhaps). Therefore, it is tempting to regard the act of adding 1 as an essentially-random shuffling of the prime factorization.
The most striking thing about the Collatz conjecture is that it seems to be making a deep statement about a subtle relation between the prime factorizations of $a$ and $a+1$. Note that the Collatz iteration consists of three steps; two of which are 'small' in terms of the prime factorization, and the other of which is adding one:
- multiplying by 3 has a small effect on the factorization.
- adding 1 has a (possibly) huge effect on the factorization.
- factoring out a power of 2 has a small effect on the factorization (in that it doesn't change the other prime powers in the factorization).
So, the Collatz conjecture seems to say that there is some sort of abstract quantity like 'energy' which cannot be arbitrarily increased by adding 1. That is, no matter where you start, and no matter where this weird prime-shuffling action of adding 1 takes you, eventually the act of pulling out 2s takes enough energy out of the system so that you reach 1. I think it is for reasons like this that mathematicians suspect that a solution of the Collatz conjecture will open new horizons and develop new and important techniques in number theory.
The Collatz conjecture is the simplest open problem in mathematics. You can explain it to all your non-mathematical friends, and even to small children who have just learned to divide by 2. It doesn't require understanding divisibility, just evenness.
The lack of connections between this conjecture and existing mathematical theories (as complained of in some other answers) is not an inadequacy of this conjecture, but of our theories.
This problem has led directly to theoretical work by Conway showing that very similar questions are formally undecidable, certainly a surprising result.
The problem also relates directly to chaotic cellular automata. If you look at a number in base 6, you will see that multiplying by 3 and dividing by 2 are the same operation (differing only by a factor of 6, i.e. the location of the decimal point), and the operation is local: each new digit only depends on two of the previous step's digits. Using a 7th state for cells that are not part of the number, a very simple cellular automaton is obtained where each cell only needs to look at one neighbor to compute its next value. (Wolfram Mathworld has some nonsense about a CA implementation being difficult due to carries, but there are no carries when you add 1, because after multiplying by 3 the last digit is either 0 (becomes a non-digit because number was even so we should divide by 6) or 3 (becomes 4), so there are never any carries.)
It is easy to prove that this CA is chaotic: If you change the interior digits in any way, the region of affected digits always grows linearly with time (by $\log_6 3$ digits per step). This prevents any engineering of the digit patterns, which are quickly randomized. If the final digit behaves randomly, then the conjecture is true. Clearly any progress on the Collatz conjecture would immediately have consequences for symbolic dynamics.
Emil Post's tag systems (which he created in 1920 expressly for studying the foundations of mathematics) have been studied for many decades, and they have been the foundation of the smallest universal Turing machines (as well as other universal systems) since 1961. In 2007, Liesbeth De Mol discovered that the Collatz problem can be encoded as the following tag system:
$\begin{eqnarray} \hspace{2cm} \alpha & \longrightarrow & c \, y \\ \hspace{2cm} c & \longrightarrow & \alpha \\ \hspace{2cm} y & \longrightarrow & \alpha \alpha \alpha \\ \end{eqnarray}$
In two passes, this tag system processes the word $\alpha^{n}$ into either $\alpha^{n/2}$ or $\alpha^{(3n+1)/2}$ depending on the parity of $n$. Larger tag systems are known to be universal, and any progress on the 3x+1 problem will be followed with close attention by this field.
In short the Collatz problem is simple enough that anyone can understand it, and yet relates not just to number theory (as described in other answers) but to issues of decidability, chaos, and the foundations of mathematics and of computation. That's about as good as it gets for a problem even a small child can understand.
So many mathematicians, and famous ones among them, have tried various ways to attack this problem, and it is still as elusive as it was when first posed. So the importance of the problem is that genuinely new mathematical ideas will have to be created to solve it, and such ideas may be helpful in other domains where "truly important" problems are at stake. Note that Erdős himself has said something along the lines that "we don't have the mathematics yet to solve this problem".