In that case it definitely sounds like you need MTC to make this work properly.

If you saw "skipping" then there was either a problem with the signal coming from Protools or a problem recieveing on Catalysts' end.

I would suspect the Protools output or cables first.

What device are you using to recieve the MIDI on Catalyst?

With MIDI it is always critical to keep your cable distances as short as possible.

If you need to go longer distances, try these boxes:
http://www.kissbox.nl/products_new.html#midi

Hope this helps.