Error: "Cannot perform a differential backup for database" (4354250)

User receives an error message when trying to create a differential database backup in SQL Server 2005:

"Cannot perform a differential backup for database <database name>, because a current database backup does not exist. Perform a full database backup by reissuing BACKUP DATABASE, omitting the WITH DIFFERENTIAL option. "

Additionally, the following message may display in the SQL Server error logs:

<Date><Time> Backup Error: 3041, Severity: 16, State: 1.
<Date><Time> Backup BACKUP failed to complete the command BACKUP DATABASE datapipe WITH DIFFERENTIAL. Check the backup application log for detailed messages.

Database backup (Full backup) has not been performed.

Ensure there is a database (Full) backup performed before taking any differential or transaction log backup.

Also, see: http://social.msdn.microsoft.com/forums/en-US/sqldisasterrecovery/thread/a8f1f773-5aa5-46bb-8751-6b1369220026/