The earlier theoretical and experimental work describing a non-inertial purely elastic instability in the Taylor-Couette flow of ''ideal'' elastic liquids is extended to fluids with a distribution of relaxation times and shear thinning in the shear viscosity and first normal stress coefficient. We find, both experimentally and theoretically, that an elastic instability can occur even in highly shear-thinning entangled polymer solutions. Using small-gap axisymmetric linear stability equations for a K-BKZ fluid with a zero value of the second normal stress difference, we show theoretically that a distribution of relaxation times, shear thinning, and a Newtonian solvent contribution to the viscosity end tend to increase the critical Deborah number, which is the shear rate times the longest relaxation time, while decreasing the critical value of the ratio of first normal stress difference (N1) to the shear stress (tau12). Experiments with both shear-thinning and non-shear-thinning polystyrene solutions, with viscosities and relaxation times differing by two orders of magnitude, show instabilities that occur at shear rates 20-45% lower than those predicted by the axisymmetric linear stability analysis. This discrepancy is readily attributable to non-axisymmetric modes, which in Oldroyd-B fluids have been shown to be unstable to shear rates 30-40% lower than the axisymmetric modes.