Hi Chris,
I went through your post and it seems to be a problem with the VSS Application Writer.
1)Refer to the following technote
http://seer.support.veritas.com/docs/261993.htm
The above technote gives the detailed description as to how to determine which writer is exactly failing and what you need to do to fix it.
2)Install service pack2 for Backup Exec 9.1
3)After doing these steps go ahead and run a new job and see if its running successfully.
NOTE : If we do not receive your reply within two business days, this post would be marked ‘assumed answered’
and would be moved to ‘answered questions’ pool.