The problem is that non-zero initial conditions cause a term in the output signal that does not depend on the input signal. This explains why a system with non-zero initial conditions can neither be linear nor time-invariant. A linear system must have a zero output for zero input. With non-zero initial conditions the output will generally be non-zero, even for a zero input signal. Alternatively, think of scaling a given input signal. A linear system will have a response that is scaled in the same way. However, the part of the output signal caused by non-zero initial conditions will not scale accordingly, because it's independent of the input signal.
The same is true concerning time-invariance. For a time-invariant system, a shifted version of the input signal must result in an output signal with the same shift. However, the output term caused by non-zero initial conditions will not shift accordingly, as it is independent of the input signal.
Consequently, a system described by a linear difference equation with constant coefficients plus initial conditions is only linear and time-invariant if the initial conditions are zero.