Sql-server – How to 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.}