Handling huge dataset imbalance (2 class values) and appropriate ML algorithm I have train and test sets of chronological data consisting of 305000 instances and 70000,appropriately. There are 15 features in each instance and only 2 possible class values ( NEW,OLD). The problem is that there are only 725 OLD instances in the train set and 95 in the test. 

The only algorithm which succeeds for me to handle imbalance is NaiveBayes in Weka (0.02 precision for OLD class), others (trees) classify each instance as NEW.
What is the best approach to handle the imbalance and the appropriate algorithm in such a case?

Thank you in advance.
I'm not allowed to comment, but I have more a suggestion: you could try to implement some "Over-sampling Techniques" like SMOTE:
http://scholar.google.com/scholar?q=oversampling+minority+classes