We analyze determinacy and stability under learning (E-stability) of rational expectations equilibria in the Blanchard and Gali (2010) New-Keynesian model of inflation and unemployment, where labor market frictions due to costs of hiring workers play an important role. We derive results for alternative specifications of monetary policy rules and alternative values of hiring costs as a percentage of GDP. We find that in general the region of indeterminacy and E-instability in the policy space increases with hiring costs. Thus, higher hiring costs--consistent with European and South African 'sclerotic' labor market institutions--seem to play an important part in explaining inflation and unemployment instability. Moreover, under lagged data based rules the area where monetary policy delivers both determinacy and E-stability shrinks. These rules also perform worse according to these two dimensions when hiring costs go up. Finally, under expectations-based rules--unlike Bullard and Mitra (2002)--an additional explosive region is introduced. For South Africa a rule based on current data--not unlike the original Taylor rule--works better than a forward-looking rule.