iOS 9.1 - Can't clear "documents & data" and "other" with restore - can it be done?
You should be able to "erase all content and settings" by using the settings app on the iPhone and then re-choose from the choices:


restore from an iCloud backup
restore from an iTunes backup
set up as a new device
restore from Android 


The error message you mentioned is typically a result of not actually running iOS 9.1 on the device (or whatever build you were in the process of installing. You can verify the exact build of iOS on the phone from the settings app > general > about

It also could be that iTunes wants to see if it can get a newer OS than what it detects on the device. In that case, just put the device into recovery mode.


Power off the phone
Plug it into the Mac while holding the home button until you see the recovery screen