In certain things I would argue that he is gullible, but in others he is extremely crafty and wise. The problem is that he is versed in war and conflict and battle, not in the games of women and the intrigues of idle men. Were he to be forced out to ferret out the tactics of the Turk and to win battles, he'd be fine and be willing to trust his opinions and his intuition over what people told him.
But in this case, with Desdemona and the supposed affair with Cassio, he is completely led on by Iago. Because he lacks confidence in this marriage and in the love of Desdemona, Iago is able to convince him rather easily that something is up with her and Cassio.