Veritas 10d backup to removable hard drives failing

Veritas 10d Backup to disk jobs on a Windows 2003 SP2 server are repeatedly failing on our removable hard drives.  We backup 3 servers each night.  We have a 2 drive rotation of 500Gb drives.  We have a "device" created for each day of the week, M-F and subsequent folder (ie, Monday) on the removable drive.  If I delete all the devices and recreate them, backups will run fine for the week.  When drive 2 is swapped in (on Monday), that's when the problems start.  For instance, this week  Monday's job ran fine (71Gb), over-writing the Monday job that was already on the drive.  Tuesday's job ran up to 70Gb and then went to "Queued" status.  When I cancelled it out, the job log states:

Job Completion Status:
Job ended: Wednesday, February 20, 2008 at 5:04:55 PM
Completed status: Failed
Final error: 0xe000fe09 - The directory is invalid.
Final error category: Resource Errors
For additional information regarding this error refer to link V-79-57344-65033

Errors:
Backup- C: SYSTEMV-79-57344-65033 - Directory not found. Cannot backup directory \Config.Msi and its subdirectories.
Backup- \\DC02\S: S_DRIVEMedia mount failed.
User canceled a Physical Volume Library operation.
V-79-57344-33861 - The media operation was terminated by the user.

Same media mount error for Wednesday's and Thursday's job, only it says the "D:" drive now and it only backed up 18Gb before it went to "Queued":
Backup- D: DATAMedia mount failed.
User canceled a Physical Volume Library operation.
V-79-57344-33861 - The media operation was terminated by the user.

We have a batch file that stops and starts all BE services before each backup and that runs successfully.  Free disk space on the backup server's C drive is above 2Gb.  Free disk space on the removable hard drive is 237Gb.  I have re-run the Media Set wizard to make sure my only media set "media set 1" allows overwrite and append.  I don't think that over-write is the problem here as it is actually backing some stuff up.  Backup drive is FAT32.  Backup-to-disk properties includes a maximum size of 1Gb for each file, maximum number of files is 100, 0Gb disk reservce, auto-detect settings.  I could have sworn I set this for 75Gb file when I recreated the devices last week - is it possible that can change with the new drive?

This is a chronic problem.  I have seen a lot of other suggestions and discussion on this, including it being a space issue, rebooting nightly and using seperate drive letters for each drive and have seperate jobs for each drive.  It seems that this should be easy and I'm overlooking something.  Any help is greatly appreciated!