1. The stat "control"(via refine etc) can provide a % chance of immunity if his is much higher than yours. This rarely comes into play but is possible.

2. What is the rest of his team? there are ninjas that can reflect debuff, for example, that might be mistaken for immunity. Knowing the rest of his team will rule out any such things.

Try fighting again, preferably multiple times.
Like I said, it could be the "control" stat, if his is higher he have a chance to be immune to your status effect. However, that is only a chance even if the difference is huge, so it should get through eventually if that was the case.
If it never gets through.... then I have no idea (I don't think any amount of control will make it hard-immune)