Soft latching with button sensing and controlled power-off
The basic circuitry seems reasonable in general principles. However - 


There MUST be a resistor (say 10K) from D13 to Q4 base (the "OFF" line" as the base clamps at well under 1V and overloads the D13 pin. This probably will not cause processor "misbehaviour", but may. 
The S1 to "sense" signalling needs work' and the value of Rs (see below) needs to be specified and to meet certain design requirements. 

The sense input will probably be failing to signal the state of S1 once Q3 is on.The value of the sense to ground resistor (call it Rs) is not shown but is important.   Too small and sense will not be pulled high initially 


eg if R2 = 10k then the R1/Rs divider will provide 9V x Rs/(Rs+R1) = 0.8v to "sense" when S1 is pressed. When Q3 is operated V_Q3_collector will be ~= 0V and Vsense will be even lower than before when S1 is pressed. So - once the latch is latched the processor will not be able to detect S1 presses. 
if Rs = 100k then when S1 is pressed Vsense = 9V/2 = 4.5V.  A 3V3 processor will complain or just expire. If Rs is say 220K then Vsense > 5V when S1 pressed and a 5V processor will be equally set about. 


Setting Rs to a "correct" value will allow a high to be signalled initially without damaging the processor, but nothing will currently allow S1 to signal a button press once Q3 is turned on.




Apart from the above, lack of latching suggests that either the latch is not working or that the processor is turning Q4 on when it ought not to

Certain conditions need to be met to allow the overall system to function.
The 'task' is to establish which of these (one or more) are not being met.
Guidelines are provided below t help yo to establish what is wrong.
To answer the question with certainty needs more information than has so far been provided.  

You say " ... is not latching" which indicates that S1 is turning on Q1 when held pressed.  

As latching depends on the latch Q1-Q3 functioning and on Q4 not resetting the latch, then one or other of these is no happening. 

Q4 action can be checked by (best) removing Q4 or (less certain) grounding  Q4 base. If this does not allow Q1-Q3 to latch then something is wrong with the actual latch circuit (as opposed to what is drawn here) or the components used. 

If the above allows latching to occur then the functioning of Q4 can be checked. With S1 held pressed Q4 collector should be at ~= 9V when "off is low and at about 0V when "off" is high. "Off" should be driven via a resistor (say 10k) from processor D13. The state of D13 must be low during and after startup. A resistor from Q4 base to ground may be needed to keep Q4 off if D13 is left as an input - but it should be set as an output and set low during initialisation.

The above should allow errant signals to be identified. If not then please observe and report relevant signal levels during operation when they depart from values expected.