When a High Availability (HA) environment failed over, on the node that became Secondary, the backup jobs did not gracefully handle the change. The Maintenance Plans are supposed to intelligently determine whether each database is Primary or Secondary in an HA environment, and skip the backup if it is not Primary. This check actually fails (practically speaking) if you have "Verify backup integrity" checked.
If you click "View T-SQL", you can see the code it generates, which looks something like this:
-- >>>> PART ONE
DECLARE @preferredReplica int
SET @preferredReplica = (SELECT [master].sys.fn_hadr_backup_is_preferred_replica('DBNAME'))
IF (@preferredReplica = 1)
BEGIN
BACKUP LOG [DBNAME] TO DISK = N'backup_destination\DBNAME_backup.trn' WITH NOFORMAT, NOINIT, NAME = N'DBNAME_backup', SKIP, REWIND, NOUNLOAD, COMPRESSION, STATS = 10
END
GO
-- >>> PART TWO
DECLARE @backupSetId as int
SELECT @backupSetId = position from msdb..backupset where database_name=N'DBNAME' and backup_set_id=(select max(backup_set_id) from msdb..backupset where database_name=N'DBNAME' )
IF @backupSetId is null begin raiserror(N'Verify failed. Backup information for database ''DBNAME'' not found.', 16, 1) end
RESTORE VERIFYONLY FROM DISK = N'backup_destination\DBNAME_backup.trn' WITH FILE = @backupSetId, NOUNLOAD, NOREWIND
The script will successfully check if the database is Primary within an HA environment (PART ONE), but it will still try to verify the backup, even if the backup was never taken (PART TWO). When it does that, it throws an error, causing the backup job to fail.
"Verify backup integrity" is wise to use when backing up over a network, as opposed to a local drive. The temporary workaround is to uncheck this option in the Maintenance Plan. I will be crafting a solution to this issue which will check the integrity of the backup on a separate step.
At https://connect.microsoft.com/SQLServer/feedback/details/797370/sql-backup-conflict-between-always-on-option-and-verify-opt we find out that Microsoft is proud of this behavior. I will be wholeheartedly disagreeing with them in the comments.