An accurate and efficient new class of predictor-corrector schemes are proposed for solving nonlinear differential equations of fractional order. By introducing a new prediction method which is explicit and of the same accuracy order as that of the correction stage, the new schemes achieve a uniform accuracy order regardless of the values of fractional order α. In cases of 0 < α ≤ 1, the new schemes significantly improve the numerical accuracy comparing with other predictor-corrector methods whose accuracy depends on a. Furthermore, by computing the memory term just once for both the prediction and correction stages, the new schemes reduce the computational cost of the so-called memory effect, which make numerical schemes for fractional differential equations expensive in general. Both 2nd-order scheme with linear interpolation and the high-order 3rd-order one with quadratic interpolation are developed and show their advantages over other comparing schemes via various numerical tests.