Gentle request for explanation on LPC and LPCC coefficients :)
As you mention, linear prediction attempts to estimate the next signal sample from a linear combination of the previous P outputs.  Mathematically, we can then express the $n^{th}$ sample of our signal $x[n]$ like this:
\begin{equation}
x[n] = \sum^{P}_{k=1} a_k x[n-k]+e[n]
\end{equation}
where $e[n]$ is the error signal.  Applying linear prediction to a frame of our signal of, say, length $N$ samples ($N\gg P$) gives us the linear prediction coefficients ${a_1,a_2,\cdots,a_P}$.

For signals where this model is valid, the error signal $e[n]$ contains very little information compared to $x[n]$.  The linear prediction operation then has given us $P$ numbers which represents most of the signal, as opposed to $N$ of them; in other words, we've been able to code the signal, hence linear predictive coding.  This coding of the signal is enormously useful for many different applications.  (Your mobile phone determines the linear prediction coefficients of your voice hundreds of times a second while you call your friends!)

Moreover, the linear predictive coefficients are essentially the coefficients of the optimal all-pole filter which describes $x[n]$. (In what sense of optimality depends on the algorithm used to determine them, but it's generally some form of time-domain least mean squares).  This means that we have an estimate of the frequency-domain envelope of $x[n]$, which we can derive from our coefficients.  Speech recognition generally operates from a frequency-domain perspective, and so linear prediction coefficients can be useful for that application too.

For improved recognition performance, it is useful to represent the frequency spectrum in other forms more closely linked with the way that we hear, i.e. some kind of perceptual domain. MFCCs and other similar signal representations (I assume that LPCCs do something similar, as I'm not familiar with them) do just that and warp the linear frequency domain in a way such that perceptual differences will be more apparent.