Well, that assumes an exclusive relationship. The rule is that his nose will grow if he lies - but not that his nose will grow IF AND ONLY IF he lies. If his nose grows despite him having told the truth -- or if his nose growing rendered a previous lie into the truth -- it doesn't violate the previous stipulation that his nose will always grow if he did lie.