Decision Stumps with same value leaf nodes
What is the overall response rate? If it's low (even 15-20%) it may be difficult to find decision stumps that contain one leaf with > 50% response! 

You could consider oversampling or changing cutoff probability, but I think if your using only 2 leaf trees, your model is bound to struggle.