Appending to media: "the operation failed to acquire the minimum number of drives and media needed"

I am getting:

"the job failed with the following error: the operation failed to acquire the minimum number of drives and media needed"

whenever I try to backup to media using the "append to media, terminate job if no appendable media is available." I have checked the media set selected in the job, and there is plenty of appendable media. However, just to make sure, I created a new media set with two brand new tapes, verified append to media is "infinite", and associated it with the job. No change. So I create a new job just to make sure it isn`t a setting within the job. No change. Restarting services has no affect. So I go into the job and without making any other changes, select "append to media, overwrite if no appendable media is available" and the job runs fine. Obviously, this isn`t a solution though. 

Suggestions?

We are running Backup Exec 2014 ver 14.1 Rev 1786

Thanks.