I don't think it is the fault of the choice of algorithms. C5 or logistic would be fine. It is possible that an algorithm like C5 is not finding any useful predictors and therefore having no predictive power.
You might try with a small number of input variables you know are associated.