The Newtonian fluid model is the simplest model of fluid behaviour that includes non-zero viscosity. It assumes that local stress is proportional to the rate of change of local strain, with a ratio that is constant over time.
Fluids with long molecular chains are more likely to have complex interactions between those molecular chains, that are either non-linear in space or are time dependent or both. So these fluids are more likely to behave in a non-Newtonian manner than fluids with simple molecules such as water.
If a fluid is both viscous and elastic (a property called viscoelasticity) then it will tend to reduce its local strain (i.e. "recover") when the stress that was deforming it is removed. Since it can have a non-zero rate of change of strain at the same time as zero stress, we can see that its stress is not proportional to the rate of change of strain, so it is non-Newtonian.