Parameter Tuning by Cross Validation for Random Forest
Are you looking at the accuracy on your validation set, rather than your training set? (you should be). Are you making sure your gap between training and validation accuracy is low? (you should be!) Is there enough data to warrant 3-fold cross-validation, or should you do 10-fold (and use more data for training)?  

In general, random search (where you sample randomly from the parameter space) will get you a good result faster than grid search.  It has the added benefit that you can specify how many models you want to build, as each model's parameters are sampled independently and not constrained to cover an entire space like grid search.