I had a problem like this where I had and "after_validate" method that was failing after I had made a bunch of changes to the model. The model was valid but the "after_validate" was returning false, so if I used model.valid it said true, but then if I saved it gave me validation errors (passed through from the after_validate callback). It was weird.
Look at the application trace and you should be able to see what line of code is raising the exception.
Make sure you aren't trying to save a deleted record.
I had the same issue. But unlike the selected answer - my issue wasn't callbacks related.
In my case I had tried to save to a deleted record (deleted from DB).
@user = User.new
@user.save! # user saved to DB
@user.persisted? # true
@user.destroy # user deleted from DB
@user.persisted? # false, user still has its id
@user.valid? # return true
@user.errors # empty
@user.save # return false
@user.save! # raise ActiveRecord::RecordNotSaved