Sounds like you need to do what it suggests, start the process over again. Be sure that the FULL BACKUP you're restoring is linked to the DIFFERENTIAL you're restoring.
"The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
- Theodore Roosevelt
Author of:
SQL Server Execution Plans
SQL Server Query Performance Tuning