I know its been awhile but for people who are having this issue, what we did was go to devices, find the backup-to device folder, uncheck the enable selection then click scan, then check the enable and re-try the backup. if it doesn't work, try it again but before you re-check the enable selection do a pause and then unpause, scan again, then check enable then scan again and then re-try the backup. Or just try some trial and error with it but make sure the drive letter correspondes to what it is in my computer, if you can access the drive through my computer then you know its how backupexec is trying to find it.
hope that helps.