Does instability make an otherwise LTI system nonlinear (or time-variant)?
I don't know how the discussion arrived to this point but it is pretty convoluted to follow after this much of time. It is an ordinary difference equation with constant coefficients thus defines a linear, time invariant system. There is no need to pursue further from that if a unique solution exists. Here we have a problem with the emphasized part.

Let's first write the descriptor state space equations: the system is described by 

$$
\begin{align}
\begin{bmatrix}1&amp;-1\\0&amp;0\end{bmatrix}
\begin{bmatrix}s_1[k+1]\\s_2[k+1]\end{bmatrix} &amp;=
\begin{bmatrix}p&amp;0\\0&amp;0\end{bmatrix}
\begin{bmatrix}s_1[k]\\s_2[k]\end{bmatrix} + 
\begin{bmatrix}0\\1\end{bmatrix}x[k]\\
y[k] &amp;= \begin{bmatrix}1&amp;0\end{bmatrix}
\begin{bmatrix}s_1[k]\\s_2[k]\end{bmatrix}
+[1]x[k]
\end{align}
$$

Now this is where I think the problematic part is. This system, though being LTI, is not regular (relevant buzz words are regular, impulse-free, index-1 descriptor systems). In other words, there exists no $\lambda$ for which the expression $\det(\lambda E-A)$ is nonzero and hence one of the modes is $\frac{\bullet}{0}$ and in fact this is $\frac{0}{0}$ for this example. This means that our system has solution uniqueness issues, unlike the causal LTI system, there is no guarantee on the existence of a unique solution. There is no guarantee of an admissible solution for that matter(buzzword impulsive systems). Hence the LTI reasoning of the other answers won't cut it. 

And this what causes the trouble as far as I can tell from Matt L's argument is that he found two nontrivially distinct solutions for the same system and concluded that this cannot be a linear system. But this also assumes the uniqueness and existence of a solution and initial conditions.

It only differs from the regular systems in the way that the uniqueness and existence guarantees of the standard LTI systems cannot be assumed. The models no longer can be assumed to have admissible trajectories for all possible signals.