Researching online, I encountered queueing theory, and lo and behold, I found that my problem is exactly that of calculating the phase-type distribution: http://en.wikipedia.org/wiki/Phase-type_distribution.

So, my matrix has a block Toeplitz form, to be more specific, the diagonal is filled by a repeating 2x2 block and off to the right, I've got a 2x1 matrix. The rest of the elements of the transition rate matrix, as it is apparently called, are zero.

So basically I'm looking for an easy way do the calculation, as it turned out to be rather time-consuming trying to understand the established lingo in the literature. I couldn't even figure out if a general formula actually exists or not, although given my numerical trials, I'd suspect one does. I'd content if somebody told me that it doesn't, though.