How can I fix "Cannot perform a differential backup ... a current database backup doesn't exist"? We recently switched to the FULL recovery model, with full backups being done every weekend, and differentials being taken every day.

The problem is, the differential backups don't always seem to work. The error message recorded in the job history is


  Executed as user: username. ... 9.00.3042.00 for 32-bit 
  Copyright (C) Microsoft Corp 1984-2005. All rights reserved.
  Started:  11:20:12 AM  Progress: 2013-01-25 11:20:13.90     Source:
  {450389BA-54C2-4892-9CD0-0126CA9B0ED8}      Executing query "DECLARE
  @Guid UNIQUEIDENTIFIER      EXECUTE msdb..sp".: 100% complete  End
  Progress  Error: 2013-01-25 11:20:14.40     Code: 0xC002F210
  Source: Back Up Database (Differential) Execute SQL Task
  Description: Executing the query "BACKUP DATABASE [MyDatabase] TO 
  DISK = N'E:\Database Backups\MyDatabase_backup_201301251120.diff'
  WITH  DIFFERENTIAL , NOFORMAT, NOINIT,  NAME =
  N'MyDatabase_backup_20130125112014', SKIP, REWIND, NOUNLOAD,  STATS =
  10  " failed with the following error: "Cannot perform a differential
  backup for database "MyDatabase", because a current database backup
  does not exist. Perform a full database backup by reissuing BACKUP
  DATABASE, omitting the WITH DIFFERENTIAL option.   BA...  The package
  execution fa...  The step failed.


The full backup job completes successfully every time, and I can view it in msdb.dbo.backupset using the query found here, so I know it exists. And it looks like after a reboot, the differential back up does complete successfully up until the next full backup.

Here's a look at the job history I have:


1/16 - Full Backup - Success
1/17 - Differential Backup - Success
1/18 - Differential Backup - Success
1/19 - Differential Backup - Success
1/20 - Full Backup - Success
1/21 - Differential Backup - Failure
1/21 - Differential Backup - Failure
1/22 - Full Backup - Success
1/22 - Differential Backup - Failure
1/22 - Reboot
1/23 - Differential Backup - Success
1/23 - Reboot
1/24 - Differential Backup - Success
1/25 - Full Backup - Success
1/25 - Differential Backup - Failure


The reboots were due to an unrelated error where @@SERVERNAME was null, so I held off posting this question until I found out if fixing the @@SERVERNAME fixed the problem, but it didn't and now I have no idea where to start.

What can cause SQL Server not to recognize a full backup for a database, and how can I fix it?

Also I'm not sure if this is related, but the differential backups seem rather large, and I am wondering if they're running the differential off the full database backup taken in the very beginning (on 1/16) instead of the most recent full backup. The full backups are about 260GB, and the differentials from 1/23-1/24 are at 30GB each.

The jobs were setup using the SQL Server Maintenance Plan Wizard, and I'm using SQL Server 2005

The [View T-SQL] button for the Maintenance Plan returns this code:

Full Backup:

BACKUP DATABASE [MyDatabase] 
TO DISK = N'E:\Database Backups\MyDatabase_backup_2013_01_25_140607_2543780.bak' 
WITH NOFORMAT, NOINIT, SKIP, REWIND, NOUNLOAD, STATS = 10, 
    NAME = N'MyDatabase_backup_2013_01_25_140607_2523778'


Differential:

BACKUP DATABASE [MyDatabase] 
TO DISK = N'E:\Database Backups\MyDatabase_backup_2013_01_25_140537_4073936.diff' 
WITH DIFFERENTIAL, NOFORMAT, NOINIT, SKIP, REWIND, NOUNLOAD,  STATS = 10, 
    NAME = N'MyDatabase_backup_2013_01_25_140537_4053934'



This is very closely related to another question I have, however it was suggested in chat that I post a new question instead of editing the other one due to the questions being different and the existing answers on the other question.
If something is taking a snapshot behind the scenes that breaks SQL differential backups causing a full to need to be taken before a new differential.  You can either stop whatever is taking the snapshot or ensure you're taking a full backup afterwards before you try to do a differential.  If you use Ola Hallengren's Maintenance Solution that can automatically change a diff to a full when it runs into this scenario.