There is also a setting Manage backup. Go there and delete the backup and try again.
Go to your windows phone settings on the web page and manage backups then delete previous backup and try again.
Do you get a failure code?
Did you try it a few time and always the same outcome?
Is date and time correct?
Is your Ms account synced?
Can you open your OneDrive app on your phone?
Can you download apps from the store?
Did you try a soft reset?
If auto backup is on and you do not see a backup than it has never worked so maybe a "setting" problem.
How long do you have your phone?