Okay, so it seems that I had the backup location set to our designated folder and also the default location (which is a valid option). When I changed the location to backup to just our designated location the backup worked.
Does anybody know why this would make a difference?