There should always be solutions unless $kn$ is a square. The equation is
equivalent to
$$k (2a+1)^2 - n (2b+1)^2 = k - n.$$
Let $(x_0, y_0)$ be
the fundamental solution of the Pell equation $x^2 - 4 k n y^2 = 1$.
Then
$$ a = \frac{x_0-1}{2} + n y_0, \quad b = \frac{x_0-1}{2} + k y_0 $$
give you a solution.

For $k = 16$, $n = 19$, a solution is
$$a = 6981194415, \qquad b = 6406383360.$$
(See also Aeryk's comment to the question.)

Now assume that $kn$ is a square. We can obviously reduce to the case
that $k$ and $n$ are coprime. Then $k = k_1^2$ and $n = n_1^2$, and we have
the equation
$$ (k_1 (2a + 1))^2 - (n_1 (2b+1))^2 = k_1^2 - n_1^2. $$
The left hand side factors as
$(k_1(2a+1) + n_1(2b+1))(k_1(2a+1) - n_1(2b+1))$.
If $k_1^2 - n_1^2 = rs$ is the corresponding factorization of the
right hand side, then we get
$$2a+1 = \frac{r+s}{2k_1} \qquad\text{and}\qquad 2b+1 = \frac{r-s}{2n_1}$$
(assuming $r \ge s$). $r = k_1 + n_1$, $s = k_1 - n_1$ gives the trivial
solution (when $k_1 > n_1$). There can be other factorizations that work,
but there may be none. For example, with $k = 6^2$, $n = 1$, we have
$6^2 - 1 = 35 \cdot 1$, which gives $a = 1$, $b = 8$.
In any case, there are only finitely many solutions, whereas in the
nonsquare case, there will always be infinitely many.