Cannot perform a differential backup for database "ABC", because a current database backup does not exist

Im trying to take differential back up on sql 2005 server with SP4 (Workgroup Edition) but it gives me below error...

Msg 3035, Level 16, State 1, Line 1
Cannot perform a differential backup for database "ABC", because a current database backup does not exist. 
Perform a full database backup by reissuing BACKUP DATABASE, omitting the WITH DIFFERENTIAL option. 
Msg 3013, Level 16, State 1, Line 1
BACKUP DATABASE is terminating abnormally.

Fullbackup exists but its still giving above message. I found this article but it seems this is applicable for sql server 2005 with no service pack.

I got below error when I tried to install above hotfix.

This update requires s开发者_如何学Cervice pack 0. The service pack for product instance MSSQLSERVER is 4.Download the update for service pack 4.

First try a full backup and then the differential backup. It is possible that your backup chain to the existing full backup is somehow broken.