What is considered to be "good" classification rate? Let's say I am trying to figure out whether two classes can be differentiated. My methods may not be perfect, but I would like to know whether my features "mean" anything that may possibly be added to reinforce another system (for instance). 
I know that if I get about 51% success rate, I am no better than random chance. But, what if I get 25% error? 30%? 40%? is this still considered to be inconsequential or no?
 A: First, you need to be more specific about what "success" (and hence "failure") means: calculate a Confusion Matrix, then consider what each quadrant means and how important they are to you. (What user777 is getting at: also read about Loss Functions.)
This will begin to address whether you are willing to trade off one kind of accuracy (or error) for another, because the other is more important/costly. It will also help you think about other issues, like whether your two classes are equally likely.
For example, if your two classes are "Legitimate Transaction" and "Fraud", and Fraud only makes up 5% of all transactions, a simple-minded classification strategy is to call everything a "Legitimate Transaction". You're going to be right 95% of the time, which blows your measly 51% out of the water. (And probably is NOT what you actually want. It just puts "51%" in perspective.)
Once you've figured out what "success" and "failure" really mean in your problem, the answer to your question pretty much falls out for free. After that, you could also consider trying other approaches like Monte Carlo Permutation Test.
