I have a somewhat different take from Peter Mueller's on an elementary way of solving

$$ab^2 + cd^2 = bc^2 + da^2.$$

To begin with, it's easy to see that there are $1+4(p-1)+2(p-1)^2+4(p-1)^2 = 6p^2-8p+3$ solutions with $abcd=0$. (There is 1 solution with four 0's, $4(p-1)$ solutions with three 0's, $2(p-1)^2$ solutions with two 0's, and $4(p-1)^2$ solutions with one 0.) So it remains to count the number of solutions with $abcd \not= 0$.

Apropos of nothing obvious for the moment, it's worth noting that the equation

$$A+B = C+D$$

(in the finite field) has $1+0+6(p-1)+4(p-1)(p-2) = 4p^2 - 6p +3$ solutions with $ABCD=0$ and hence $p^3-4p^2+6p-3$ solutions with $ABCD \not= 0$.

Getting back to the lowercase equation, if $abcd\not=0$, then each variable is a power of a generator, say $g$, of the finite field: $a=g^\alpha$, $b=g^\beta$, $c=g^\gamma$, and $d=g^\delta$. If we write the equation in these terms and divide everything by $g^{\alpha+\beta+\gamma+\delta}$, we have

$$g^r + g^s = g^t + g^u,$$

where

$$r=\beta-\gamma-\delta$$
$$s=\delta-\alpha-\beta$$
$$t=\gamma-\delta-\alpha$$
$$u=\alpha-\beta-\gamma$$

This last batch of equations is really a linear system of congruences $\mod(p-1)$. The linear transformation turns out to have determinant with absolute value 5. Consequently, if 5 does not divide $p-1$, i.e, if $p\not\equiv1 \mod5$, then there's a one-to-one correspondence between points $(\alpha,\beta,\gamma,\delta)$ and $(r,s,t,u)$. But in that case, we may as well think of the equation $g^r + g^s = g^t + g^u$ as the equation

$$A+B=C+D$$
with $ABCD\not=0$. As we casually noted earlier, there are $p^3-4p^2+6p-3$ such solutions. Combining this with the $6p^2-8p+3$ solutions with $abcd=0$, we get a total count of

$$(p^3-4p^2+6p-3)+(6p^2-8p+3) = (p^2+2p-2)p$$

solutions when $p\not\equiv1\mod5$, in agreement with what Peter Mueller found. (A small confession: I was initially perplexed by the difference between his mod 10 and my mod 5. A larger confession: Peter's results were a huge help in catching and correcting mistakes I made in my own calculations.)

I'm a bit mired at this point in how to deal with the case $p\equiv1\mod5$, so I'm going to leave things unfinished for now. I'll try to come back to it if I can find more time. Alternatively, if someone sees a slick way to finish and/or streamline things, please post it, either in comments or as a separate answer.

**Added 11/30/12:** I haven't had any luck making this approach work when $p\equiv1\mod5$, but Peter Mueller's comment has prompted me to go back and look more closely at the determinant of the linear transformation I used. As Peter noted, in the general case ($a^mb^n + c^md^n = b^mc^n + d^ma^n$), the determinant is $n^4-m^4$. That's actually for the linear transformation that turns $g^{m\alpha+n\beta}+g^{m\gamma+n\delta}=g^{m\beta+n\gamma}+g^{m\delta+n\alpha}$ into $g^r+g^s=g^t+g^u$. Note that when $m=1$, $n=2$, $n^4-m^4=15$, which suggests there's a problem not just when $p\equiv1\mod5$, but also when $p\equiv1\mod3$. That is, in fact, what I initially did. But given the results in Peter's answer, I suspected there ought to be a way of getting rid of the 3. I intuited that dividing by $g^{\alpha+\beta+\gamma+\delta}$ would help, and indeed it did, but I didn't really think about why.

Here's what's really going on. In general, you can divide by $g^{h\alpha+j\beta+k\gamma+\ell\delta}$ for any choice of $h,j,k,\ell$. Doing so gives a determinant (up to sign) of

$$n^4-m^4 -(h+j+k+\ell)(n-m)(n^2+m^2) = (n-m)(n^2+m^2)(n+m-h-j-k-\ell).$$

It's clear that one can choose $h,j,k,$ and $\ell$ to make the last factor $\pm1$; there's no particular need to make them all equal, but when $m+n$ is odd it's an appealing option.

The upshot is that the approach falters only for primes $p$ for which $p-1$ has a factor in common with $(n-m)(n^2+m^2)$. Whether it can be coaxed into saying something useful in the cases where it falters, I still don't know.