Windows Server 2012 R2 Backup Error 0x80780119

Brand new server, install Windows 2012 R2 (inc Update 1), get everything setup and attempt to run a backup... and what do we get?

Above: Snip from the Windows Server Backup Error

Above: Snip from Event Viewer

So naturally one would be rather confused, a new server out of disk space?!

After some research I came across this Microsoft KB Article:

https://support.microsoft.com/kb/2930294
"System image backup fails after you upgrade to Windows 8.1 or Windows Server 2012 R2"
Very simple procedure; all I can add is once all is completed, if you had to move the Recovery Partition to the end of the disk like I did, you'll need to update the Windows Server Backup Schedule as the 'Recovery' partition ID will have changed and WSB fails if you have not updated the schedule.