Thanks for all the suggestions Rob and PapaG... implementing a packet structure seems like a nice way to go.
Mike, I'll try upping the priority and see how it goes.
At the moment running functions that plot LED by LED in a packet of (x,y,r,g,b) seem to overwhelm the Arduino's serial buffer more often than not. Sending an ACK per frame slows things down too much. E.g. when plotting 100 LED's (less than 1/4 the screen) with an ACK per packet it drops the frame rate to 3 or 4 frames per second. Not sure the best way around this. I think I might try and set up something that sends a 'pause' command if the buffer get's near 128bytes full.