I have tried as well and NOTHING works!!! I sure wish someone would verify that the "Backup IS showing on OneDrive IS working" but the Phone (Lumia ICON 8.1 Denim) incorrectly says it "failed"!
Anyone?
EUREKA !!! I searched for other threads and saw "people CONFIRMING" that "DELETING your Backup under Manage Backups" would work!
So, I hesitantly "from the Backup in Windows Phone" DELETED the Backup!
As the other article stated = the Backup for Apps and Settings "WILL TURN OFF" = which it did!
Next step was to "turn Backup back ON" - BOTH Apps and Settings ... and, VOILA hit "Backup now" and it took easily 5X as long to get to 98% ...
Then STAYED at 98% for what seemed an eternity - versus almost immediately FAILING at 98% - and then ...
LAST BACKED 2 SECONDS AGO!
I have been "chasing this for over a month now" !!!