I had the same problem. For me, it wasn't the transition matrix at all; it was the emission matrix. I used too many hidden states and some of them gave zero columns in the emission matrix. Once the hmmviterbi got into one of these states, it didn't know where to go. I solved it by making educated guesses on what state should be preferred at those given states, so that now there's at least one entry at these hidden states.