Primes are positive.
So, 25 is not so expressible. The sequence of non-expressible integers begins 25,34,58,64,85,91,121,130,169,196,214,289,324,... and is A014090 at the OEIS.
There, Dean Hickerson gives a proof that this sequence is infinite. Note that the allowance of the number 1 as an honorary prime does not cause difficulty, since a square cannot differ by 1 from a square.
Added: Dean's proof goes like this. Let $n$ be a positive integer such that $2n-1$ is composite. Then if we can write $n^2$ as the sum of a square and a prime, we'll have
$$ n^2 = m^2 + p$$ for some integer $m$ and some prime $p>0$. Then,
$$ p = n^2-m^2 = (n-m)(n+m).$$ Since $p$ is prime, we must have
and so $p=n+m=2n-1$, which contradicts the primality of $p$. So $n^2$ is not so representable.
Now, if we allow negative primes, we simply modify this and consider positive $n$ such that $2n-1$ and $2n+1$ are composite. Then if $n^2=m^2+p$ for some integer $m$ and some prime $p$, possibly negative, we have
$$ p =n^2-m^2 = (n-m)(n+m)$$ and so $n-m=\pm 1$ and $n+m=2n+1$ or $n+m=2n-1$. Since both values are composite, this contradicts $p$'s primality. So $n^2$ is not so representable.
Now, there are infinitely many such $n$. Consider, for example, $n$ of the form
$$ n = 13+15r$$ for $r$ a positive integer. Then
$$ 2n-1 = 25+30r = 5(5+6r)$$
$$2n+1 = 27+30r = 3(9+10r)$$
are both composite, and so there are infinitely many integers not representable as the sum of a square and a prime (positive or negative).