The linear stability of two-phase stratified flows through soft-gel-coated walls is studied in this work. A consistent nonlinear neo-Hookean model describes the soft-gel. The base state is characterised by a first normal stress difference in this model. This results in a significantly different effect on the stability of two-phase flows as compared to when a linear viscoelastic model is used for the soft-gel. Both fluids are assumed Newtonian and incompressible. We analyze the system in the absence and presence of a soluble surfactant. A linear stability analysis is carried out to identify different instability modes in the system. The linearised equations result in a generalised eigenvalue problem which is numerically solved employing a Chebyshev collocation technique. Three distinct instabilities are identified in the absence of a soluble surfactant. A long wave interfacial instability, a Tollmien-Schlichting wave type instability, and a gel-liquid instability arise in the system. Two distinct additional instabilities are identified in the presence of soluble surfactants in the system, a Marangoni driven long wave instability and a liquid-liquid short wave mode. It is shown that all instabilities except the Tollmien-Schlichting shear instability can be stabilised by the soft-gel layers for a suitable choice of parameters. Insights into the physical mechanism driving the different instabilities are discussed. © 2018 Author(s).