I don't know what type of relay you have, but when a motor is started, there can be a signficant asymmetrical (dc offset)current for a cycle or two. The magnitude of the dc offset is a function of the phase angle of the voltage when the breaker, or contactor, closes.
This can explain an "intermittent" trip in some cases. We often see this with transformer primary protection as well.
Because the inrush current is not equal in all three phases, the motor relay could be interpreting this as a phase-to-phase fault.
If the motor is tripping instantly upon starting, I would suspect this could be the cause. The solution may be to increase the trip setting. The NEC allows up to 13 times the full load current of the motor if necessary to avoid nuisance tripping. I'd check with the motor relay manufacturer and get their opinion.