Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?
Your optimal alignment seems to be an optimal local alignment, the best substring match. Needleman-Wunsch is for global alignment. With the simple program by Eddy that you can find on the internet I have determined a global score of 0. This is better than the gobal score you get:  -5 (for 10 gaps and 5 matches).

Sequence X: GCATGCU
Sequence Y: GATTACA
Scoring system: 1 for match; -1 for mismatch; -1 for gap

Dynamic programming matrix:
             G    A    T    T    A    C    A 
        0   -1   -2   -3   -4   -5   -6   -7 
   G   -1    1    0   -1   -2   -3   -4   -5 
   C   -2    0    0   -1   -2   -3   -2   -3 
   A   -3   -1    1    0   -1   -1   -2   -1 
   T   -4   -2    0    2    1    0   -1   -2 
   G   -5   -3   -1    1    1    0   -1   -2 
   C   -6   -4   -2    0    0    0    1    0 
   U   -7   -5   -3   -1   -1   -1    0    0 

Alignment:
X: GCA-TGCU
Y: G-ATTACA
Optimum alignment score: 0