[Mark McLeod]

The 15,871 (specified as 2-byte words BTW, so 31,742 bytes) certainly looks pretty full. There is some overhead that doesn't appear but is responsible for 1k or so of lost program memory space. If I recall correctly you really only get 30,720 bytes or roughly 90% of the total available as reported by MPLAB for the PIC18F8522. MPLAB doesn't tell you about everything.
If it were a data memory limit you'd see udata or idata as part of the error message. The idata error is for static initialized variables but often works out to be a secondary indicator that your program memory is also filling up (seems to be a psychological thing).

A quick test/solution would be to turn on some of the built-in compiler optimizing to automatically reduce the amount of program memory you're using and that'll probably fit your code at least into the 8522 chip.

In MPLAB go to:
Project->Build Options->Project
then the MPLAB C18 tab
Unclick "Use Alternate Settings" (if it's checked off).
then at the top of that you'll see "Categories:" with a pull-down menu where you can select "Optimization"
On that menu just click "Enable all"
Apply it, but make sure all the "-Ou- -Ot-" etc. are not still set in the General MPLINK C18 tab. MPLAB can make it difficult to hold onto these setting changes. If you want to use Alternate Settings just remove the -O flags.

Re-compile and see how much program space you save. You'll probably see a 30% reduction.

The optimizations can be individually selected if you like. Each are described in the C18 manual.

P.S. I'd editing this a bit as I remember stuff.