Z[sqrt(-3)] does not have unique factorization. However, Z[w] does, where w = (-1 + sqrt(-3))/2 denotes a primitive third root of unity.
In particular,
2 * 2 = (-1 + sqrt(-3)) * (-1 - sqrt(-3))
gives two irreducible factorizations of 4 in Z[sqrt(-3)] (you can use norm arguments in Z[w] to show irreducibility). Note that the right hand side can also be written as
(2w) * (2w^2)
however, since w is not in Z[sqrt(-3)], the two factorizations above are distinct in Z[sqrt(-3)]. They become the same factorization in Z[w].
Edit: Another way to think about why Z[sqrt(-3)] doesn't have unique factorization is because it isn't integrally closed[1]--that is, there is a monic polynomial (ie a polynomial with a leading coefficient of 1) with coefficients in Z[sqrt(-3)] that doesn't have roots in Z[sqrt(-3)]. In particular, since w^2 + w + 1 == 0, w is a root of the polynomial x^2 + x + 1, which is monic over Z[sqrt(-3)]. It turns out that any unique factorization domain[2] is integrally closed. Since Z[sqrt(-3)] is not integrally closed, it is not a UFD.
But Z[sqrt(-3)] is not the ring of Eisenstein integers.
Regardless, the fact that Z[sqrt(-n)] is a UFD for n = 1,2 but not for n >= 3 is indeed quite counter-intuitive. But Gowers isn't asking whether it's intuitive for Z[sqrt(-n)]. He's asking about the positive integers, and the positive integers have a very special well-ordering which respects the arithmetic operations and for which humans have quite a powerful intuition.
I maintain that Z[sqrt(-n)] is more different from Z than Gowers is letting on and that if you actually look at all the differences, rather doing the opposite and trying to make it seem similar to Z, you'll quickly realize why people feel that the FTA is not very bizarre for Z but it is for Z[sqrt(-n)].
