Your mistake is simply the statement that the state $|j_1 m_1\rangle$ and $|j_2 m_2\rangle$ are the same physical state: these are abstract angular momentum labels, they aren't full descriptions of the state. The two states would only be the same when the two objects carrying these quantum numbers are indistinguishable in every way, like two spin-1/2 electrons in an S-wave in the He atom ground-state. In this case, only the antisymmetric spin-0 combination survives, where the phase factor $(-1)^{j_1+j_2 + J}$ is -1. The two electrons are fermions, so you see the two states need to get a minus sign, and this is only possible when they are a spin 0 combination. There is no spin-1 version of the He4 ground state, because the two electrons can't have the spin aligned since they are fermions.
The way to understand the phase factor is through a few examples, and a better SU(2) representation theory. The examples are the vector combination law:
$$ A \cdot B $$
$$ A \times B $$
$$ (AB)_{ij} = {1\over 2}(A_i B_j + B_j A_i) - {1\over 3} A\cdot B \delta_{ij}$$
These are the spin-0, spin-1, and spin-2 parts of the product of two vectors, in SO(3) index notation. You can see that the spin-1 part is antisymmetric under interchange, and the spin-2 and spin-0 part are symmetric.
Likewise, the antisymmeric spin-1/2 spin-1/2 combination is the singlet, and the symmetric one is the triplet. This is easiest to see in SU(2) index notation, where
$$ \epsilon_{ij} a^i b^j $$
is the singlet formed from SU(2) vectors $a^i$ and $b^i$, while the triplet is
$$ (AB)^{ij} = (a^i b^j + a^j b^i )$$
Which is symmetric. Beware that $AB^{12}$ is not normalized properly as compared to the usual textbook $|j,m\rangle$ presentation. One of the states of the 2-tensor (2-tensor of SU(2), the spin-1 object) is
$$ |1,0\rangle $$
when represented as an SU(2) tensor, this has components
$$ (AB)^{12} = (AB)^{21} = {1\over \sqrt 2 }$$
These numbers are determined by making sure that the tensor is normalized, and give you square-root of integer factors. The other states don't have these annoying factors, but these build up the Clebsch-Gordon coefficients.
The representation theory of SU(2), when expressed in tensors, makes the $J=j_1+j_2$ representation by multiplying the two tensors for $j_1$ and $j_2$ without any epsilons. This makes a completely symmetric thing, where you get rid of the antisymmetric parts.
As you step down J, you get an $\epsilon$ tensor each time you go down, changing the symmetric/antisymmetric character. This way of doing the representation theory is the simplest way, it allows you to carry the Clebsch-Gordon coefficients in your head. It is described in detail in this answer: Mathematically, what is color charge? .