It may also be that you are out of processing speed. If your input capture compare is to fast, its possible that it will not get time to service the input before the next input is triggered. We run a siren of an 8 bit processor while decoding a receiver and have had this problem.
As was said above, try setting your input capture to a very high priority, otherwise, you may be left with no other option other than to either slow down your input capture rat, which is often not even possible. Maybe you will need a dedicated 8 bit processor externally to process high speed data...
Just some idea's....