It deserves to be much better known that **nonexistant GCDs** and **nonprincipal ideals**
arise *immediately* from any failure of Euclid's Lemma, and this provides an illuminating way to view many of the standard examples. Below is a detailed explanation extracted from one of my sci.math.research posts [2]. The results below hold true in *any* domain D.

**LEMMA**:  (a,b) = (ac,bc)/c  if  (ac,bc)  exists

Proof: d|a,b <=> dc|ac,bc <=> dc|(ac,bc) <=> d|(ac,bc)/c. QED

**EUCLID'S LEMMA**:  a|bc and (a,b)=1 => a|c, if (ac,bc) exists 

Proof:   a|ac,bc => a|(ac,bc) = (a,b)c = c  via Lemma. QED 

Therefore if a,b,c fail to satisfy the implication in Euclid's Lemma, 
namely  if  (a,b) = 1  and  a|bc, not a|c, then one 
immediately deduces that the gcd (ac,bc) fails to exist in D.

E.g. David Speyer's example above, and Khurana's example in [1] (= Theorem 31 in Pete L. Clark's [0]) are simply specializations where  a,b,c = p,1+w,1-w  in a quadratic number ring Z[w], ww = -d. 

[0] Clark, Pete. L. Factorization in integral domains. 29pp. 2009.
http://math.uga.edu/~pete/factorization.pdf

[1] D. Khurana, On GCD and LCM in domains: A Conjecture of Gauss. 
Resonance 8 (2003), 72-79. 
http://www.ias.ac.in/resonance/June2003/pdf/June2003Classroom.pdf 

[2] sci.math.research, 3/12/09, seeking comments on expository article on factorization  
http://groups.google.com/group/sci.math.research/msg/88343de90a4cf6b7  
http://google.com/groups?selm=gparte%24si4%241%40dizzy.math.ohio-state.edu