Hi TMRh20,
TMRh20:
sei(); //Now enable global interupts before this interrupt is finished
Thanks for pointing me into the right direction with that line of code. Before I haven't really thought about re-enabling global interrupts within an interrupt call since that sounds a bit like a bad idea I'd say 
Nevertheless I was able to solve my problem with going back to my initial interrupt interval of ~1250us and re-enabling global interrupts at the beginning of every interrupt call. Luckily the interruptions of the internal serial interrupt are that short that they don't mess around with the timing of updating my LED array so that I was able to get this running with just using one interrupt.
Thanks again!
Greetings,
Markus