Playing with blocks
Jukka-Pekka Ikaheimonen, michael reid, Dave Tuller, Martin I Eiger, David Shallcross, and Joseph DeVincentis sent solutions.

The solution comes after realizing that all diagonals are palindromes.

 Here are a couple proofs:

Theorem: If you start with a 1 x n strip, then the process will
terminate, at the latest, when the nth strip is placed.

Proof: First, notice that this procedure gives a unique pattern
determined by the initial 1 x n block. Therefore, it suffices to
determine an n x n square such that for each unit square, an even number
of its neighbors is a different color and that the bottom row is the
given 1 x n block. To this end, let the colors be denoted 0 and 1. We
label the n x n square with coordinates along the x and y directions 0,
1, 2, ..., k = n-1 (this k is for convenience only). Let the color
sequence of the 1 x n block be a_0, a_1, ..., a_k. Now define c_{x,y} =
the color of the square with coordinates x and y = a_{y-x}+...+a_{y+x}
(mod 2) whenever x <= y <= k-x. The remainder of the colors can be
determined by c_{x,y}=c_{y,x}=c_{k-y,k-x}. It is simple to check that
this colored square satisfies the required conditions. Q.E.D.

Consider a starting configuration that decomposes into subsequences,
each of length K.  The first, third, fifth, etc., subsequences are all
A1,A2,A3,...,AK.  The second, fourth, sixth, etc., subsequences are
all AK,A(K-1),A(K-2),...,A1.  It doesn't matter whether the number of
subsequences (N/K) is even or odd, as long as they alternate.

David asserts that all such starting configurations converge in K
rows.  I believe the argument is that each subsequence grows
(vertically) independently, and adjacent cells across the boundaries
between subsequences will always be the same color.

Moreover, I believe that he argued that all starting configurations
that converge in fewer than N rows have this form.  The logic is that
if you have an N*K array of blocks where each cell has an even number
of oppositely colored neighbors, then you can rotate it 90 degrees,
strip off the top (N-K) rows (since we have already shown that K cells
will converge in K rows), and then rotate it back.

the game always terminates after at most  n-1  rows have been added
to the original.  in fact, the array you build up is symmetric
over the diagonal line  x = y  (also over the other diagonal).
we prove this by induction.
proof.  when we add square  (i, j) there are three cases.
        i >= j.  then square  (j, i)  hasn't been filled yet,
        so there is no requirement.
        i = j - 1.  so we're filling square  (i, i+1)  in such a
        way that  (*)  holds for square (i, i).  its other neighbors
        are (i-1, i), (i, i-1) and (i+1, i).  the first two have
        the same color (or are empty, if  i = 1) by the symmetry
        condition (and implicit induction hypothesis).  so square
        (i, i+1) matches (i+1, i) in order for the number of blue
        neighbors to be even.
        i < j - 1.  now we're filling square  (i, j) so that (*)
        holds for square (i, j-1).  its other neighbors are
        (i, j-2), (i-1, j-1) and (i+1, j-1), which match
        (j-2, i), (j-1, i-1) and (j-1, i+1), respectively.
        since (*) holds for square (j-1, i) which matches (i, j-1),
        we see that (i, j) must also match (j, i).
        this completes the proof.

now we see that after  n-1  rows are added to the initial one, we
have a square which is symmetric over the line  x = y .  in particular,
condition (*) is satisfied for all squares  (i, n) , 1 <= i < n,
since the condition is satisfied for square  (n, i).  condition (*)
also hold for square (n, n), since its two neighbors, (n-1, n) and
(n, n-1) have the same color.  so the game stops here, although perhaps
it could have terminated earlier.


Sometimes these things just come to you and sometimes they take
a long time.  Anyway, there is no such coloring.  Suppose there is,
for some finite length of strips n.  The colors on one strip only depend
on the colors on the two strips immediately before that one.  Since
there are only 2^n possible sequences of colors on a strip, there are at
most 2^2n sequences of colors on 2 consecutive strips, so after at most 2^2n
+ 1 strips, the pattern of colors on a pair of consecutive
strips must repeat, and once it does, the entire cycle of strips between the
repeating ones will repeat forever.  Now, in this
semi-infinite row of strips, the (*) condition is true for every square.
Given this, and starting at some strip in the repeating sequence, we
can work backwards, figuring what every strip must be based on the two
strips which *follow* it, because those two strips determine a unique strip
which could have occurred before them, in exactly the same way any two
strips uniquely determine the one which follows
them, in the original procedure.

Eventually, we will reach the first two strips.  Our calculation *must*
produce the sequence on the first two strips, due to the uniqueness I
described above.  However, also due to this uniqueness, these first
two strips must appear in the repeating sequence (the sequence repeats when
run backwards, too).  Now, what strip must be the one
which appears before the first strip, where the first two strips appear in
the repeating sequence?  Since this strip works at the end of the
sequence, it must be another identical strip (no squares of opposite
color next to any of the squares in the first strip, since none are
needed), and the strip before that one is a repeat of the second strip
(since the duplicate first strip has no contribution of opposite-colored
squares from the first strip, it needs the same strip as our original second
strip to meet the (*) condition).  However, if the repeating sequence
contained such a sequence (which at some point contains
a duplicate second strip followed by a duplicate first strip), it would
have ended there, because we know that pattern of strips meets (*).
Thus, our initial assumption that we can create such an infinite chain
must be incorrect.