First of all, (late) happy birthday and (again) congratulations for the BMO! Let us denote the number of colors on the $i$-th column by $c_i$, the number of colors on the $i$-th row by $l_i$. Furthermore, let us denote the number of columns on which the $i$-th color shows up by $a_i$, and the number of rows it shows up on by $b_i$. It is clear that $a_ib_i\geq N$, since the color $i$ is totally included in the submatrix with dimension $a_i$ x $b_i$ on the respective rows. Also, if we contradict the conclusion, we will also have $n\geq l_i, n\geq c_i$. By a trivial double counting argument, we get $\sum l_i=\sum b_i$ and $\sum c_i=\sum a_i$. Then: $(n\cdot N)^2\geq (\sum l_i)(\sum c_i)=(\sum a_i)(\sum b_i)\geq$ $\geq (\sum \sqrt{a_ib_i})^2\geq N^2\cdot (\sqrt{N})^2=N^2\cdot(n^2+1)$, a blatant contradiction.

See http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=412838 or http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=282839

Thank you, Octav, and congratulations for BMO too! A slightly harder problem was given at this year's Komal contest; see A.555 here.

Begin by noticing that each color must exist in total more than $2n$ rows and columns, because otherwise there would be a maximum of $n^2$ squares colored using that color (by AM-GM or something), impossible. Summing this over all possible colors and rephrasing in terms of rows and columns, we find that the sum of the number of distinct colors in row or column over all possible rows and columns is more than $2nN$. But there are only $2N$ rows and columns, so by the pigeonhole principle, there is a row or column with more than $n$ distinct colors. $\blacksquare$