Using boolean features encoded as 0 and 1 should work. If the predictive accuracy is bad even with a large number of decision trees in your forest it might be the case that your data is too noisy to get the learning algorithm to not pickup any think interesting.
Have you tried to fit a linear model (e.g. Logistic Regression) as a baseline on this data?
Edit: in practice using integer coding for categorical variables tends to work very well for many randomized decision trees models (such as RandomForest and ExtraTrees in scikit-learn).