The norm, a2+5b2, is still a valid multiplicative map into the positive integers. The only units are ±1, having norm 1.
Consider (2+q)×(2-q) = 9. Yet 3×3 is also 9. Well that's fine; maybe 3 breaks down in this ring. We've seen integer primes break down before, e.g. 17 = (4+i)×(4-i) in the gaussian integers. But 3 isn't the product of anything here. If xy = 3, then the norm of x, and the norm of y, both divide the norm of 3, which is 9. Thus the norm of x = the norm of y = 3. There is no a+bq with a2+5b2 = 3. Nothing divides 3, or 2+q. The composite number 9 is the product of irreducible factors in two different ways.
So what happened to our gcd algorithm? The problem is, the rectangles are too tall. The middle is too far from the corners, and if we subtract, the difference can be larger than the width of the rectangle. Try running gcd(3,2+q). Let 3 act as the base vector, spawning a series of rectangles in the complex plane. These cells are lined up with the axes, and are easy to picture. They are 3 units wide and approximately 6.7 units tall. The element 2+q lies in the first cell, and the closest corner is at 3,0, so subtract, giving 1-q. Use this as a base vector; it's smaller. Now the rectangles are tilted, so get ready to turn your head. The rectangle with its bottom corners at the origin and 1-q runs up and to the right, with its top corners at 5+q and 6. Now 3 is smack in the center of this rectangle, and is 3 units away from all four corners. If we consider 2+q instead, it is the center of the adjacent cell, and is 3 units from its four corners. The gcd algorithm has brought us back to 3 and 2+q, and is in an infinite loop. We cannot find common factors, or demonstrate unique factorization.
Nor can we characterize the solutions to x2 + 5y2 = z2, as we did before. The solution x=2, y=1, z=3 has no corresponding uv pair, since 5uv would have to equal 1.
Let q be the square root of -5 as above. Let R be Z adjoin q, with F the fraction field of R. Let p(x) = 3x2+4x+3. Note that p = 3x+(2+q) times x+(2-q)/3. Thus p factors in the fraction field of R. Suppose it also factors in R. This quadratic splits into two monomials, and since 3 is irreducible, each monomial employs coefficients of ±1 or ±3. There are only a few combinations, and none of them produce p(x). Factorization in F[x] does not imply factorization in R[x].
If you want a monic polynomial that causes gauss' lemma to fail, we need a new ring, that is not integrally closed. Let q = sqrt(-3), and x2+x+1 factors into x+(1+q)/2 times x+(1-q)/2, yet there is no factorization over the base ring Z[q].