My plan is to wait until there is data available at the serial connection, read it in and then immediately after generate a timestamp using micros().
What are you expecting to get from the serial port? How will you know when a packet is complete?
Then I want to send the event and the timestamp over serial usb to a host.
The same serial port that you just read from? What does this have to do with MIDI?
In particular, is there anything that might cause the timestamp to be inaccurate?
The fact that micros() only updates every 4 microseconds.