Ok doke. I can run the script out of a Query Analyzer logged in with windows authentication.
EXECUTE master..sqlbackup N'-SQL "BACKUP DATABASE [XYZ] TO DISK = ''C:\\SQLBACKUP\\DAILY\\DB\\<AUTO>.sqb'' WITH COMPRESSION = 1, ERASEFILES_ATSTART = 5, INIT, MAILTO = ''email@example.com
'', THREADCOUNT = 4, VERIFY"'
That works great, so somewhere.. the script is executing under the wrong permissions from SQLBackupC.