For each colour $i \in [n]$, let $r_i$ be the number of vertices incident to an edge of colour $i$ on the right side of $K_{n,n}$ and $\ell_i$ be the number of vertices incident to an edge of colour $i$ on the left side of $K_{n,n}$. Observe that $r_i+\ell_i \geq 2\sqrt{n}$ for all $i$, where equality is obtained if and only if the edges of colour $i$ induce a $K_{\sqrt{n}, \sqrt{n}}$. Now for each colour $i$ choose a subgraph $R_i$ of the edges of colour $i$ such that there are $r_i$ vertices of $R_i$ on the right and each vertex on the right has degree $1$. Similarly, let $L_i$ be a subgraph of the edges of colour $i$ such that there are $\ell_i$ vertices of $L_i$ on the left and each vertex on the left has degree $1$. Since $r_i+\ell_i \geq 2\sqrt{n}$ for all $i$, $\bigcup_{i \in [n]} R_i$ has a vertex on the right with degree at least $\sqrt{n}$, or $\bigcup_{i \in [n]} L_i$ has a vertex on the left with degree at least $\sqrt{n}$. In either case we have found a vertex incident to at least $\sqrt{n}$ colours.

Here is a short proof. Thanks to David Speyer for simplifying an earlier proof of mine (see the comments below).

For each colour $i \in [n]$, let $a_i$ be the number of vertices incident to an edge of colour $i$. Observe that $a_i \geq 2\sqrt{n}$ for all $i$, where equality is obtained if and only if the edges of colour $i$ induce a $K_{\sqrt{n}, \sqrt{n}}$. Thus, $\sum_{i \in [n]} a_i \geq 2n \sqrt{n}$. On the other hand, $\sum_{i \in [n]} a_i$ is the number of ordered pairs $(v,i)$, where $v$ is a vertex, and $i$ is a colour incident to $v$. Therefore, since there are only $2n$ vertices, some vertex must be incident to at least $\sqrt{n}$ colours.

For each colour $i \in [n]$, let $r_i$ be the number of vertices incident to an edge of colour $i$ on the right side of $K_{n,n}$ and $\ell_i$ be the number of vertices incident to an edge of colour $i$ on the left side of $K_{n,n}$. Observe that $r_i+\ell_i \geq 2\sqrt{n}$ for all $i$, where equality is obtained if and only if the edges of colour $i$ induce a $K_{\sqrt{n}, \sqrt{n}}$. Now for each colour $i$ choose a subgraph $R_i$ of the edges of colour $i$ such that there are $r_i$ vertices of $R_i$ on the right and each vertex on the right has degree $1$. Similarly, let $L_i$ be a subgraph of the edges of colour $i$ such that there are $\ell_i$ vertices of $L_i$ on the left and each vertex on the left has degree $1$. Since $r_i+\ell_i \geq 2\sqrt{n}$ for all $i$, we must have that $\bigcup_{i \in [n]} R_i$ has a vertex on the right with degree at least $\sqrt{n}$, or $\bigcup_{i \in [n]} L_i$ has a vertex on the left with degree at least $\sqrt{n}$. In either case we have found a vertex incident to at least $\sqrt{n}$ colours.

For each colour $i \in [n]$, let $r_i$ be the number of vertices incident to an edge of colour $i$ on the right side of $K_{n,n}$ and $\ell_i$ be the number of vertices incident to an edge of colour $i$ on the left side of $K_{n,n}$. Observe that $r_i+\ell_i \geq 2\sqrt{n}$ for all $i$, where equality is obtained if and only if the edges of colour $i$ induce a $K_{\sqrt{n}, \sqrt{n}}$. Now for each colour $i$ choose a subgraph $R_i$ of the edges of colour $i$ such that there are $r_i$ vertices of $R_i$ on the right and each vertex on the right has degree $1$. Similarly, let $L_i$ be a subgraph of the edges of colour $i$ such that there are $\ell_i$ vertices of $L_i$ on the left and each vertex on the left has degree $1$. Since $r_i+\ell_i \geq 2\sqrt{n}$ for all $i$,   $\bigcup_{i \in [n]} R_i$ has a vertex on the right with degree at least $\sqrt{n}$, or $\bigcup_{i \in [n]} L_i$ has a vertex on the left with degree at least $\sqrt{n}$. In either case we have found a vertex incident to at least $\sqrt{n}$ colours.