I'm afraid you might have to look at non-associative algebras if you hope to find an example.  I can't give you a reference because the following result comes from the notes for an undergraduate course I took a few years ago; I have no idea if this is a standard result.  (I'm also slightly worried that it implicitly uses finite-dimensionality somewhere and doesn't mention it, but I haven't managed to spot anything.)

Result: Let $A$, $B$ be associative $k$-algebras.  Then $Z(A \otimes_k B) = Z(A) \otimes_k Z(B)$.

Proof: Let $z = \sum_{i=1}^n a_i \otimes b_i$ be an element of $Z(A \otimes_k B)$, and assume wlog that the $b_i$ are $k$-linearly independent.  Since $z$ is central, it must commute with all elements of the form $a \otimes 1$, $a \in A$.  Therefore
\begin{equation*}0 = z(a\otimes 1) - (a\otimes 1)z = \sum_{i =1}^n (a_ia - aa_i) \otimes b_i\end{equation*}
and this holds iff $a_i \in Z(A)$ for all $i$, since $a \in A$ was arbitrary and the $b_i$ are linearly independent.  

We can assume that the $a_i$ are linearly independent in $Z(A)$.  Since $z$ must also commute with all elements of the form $1\otimes b$, $b \in B$, we get that $b_i \in Z(B)$ for all $i$ as well.  Thus $Z(A\otimes_kB) \subseteq Z(A) \otimes_k Z(B)$, and the reverse inclusion is clear.