Since this is a differential backup, have you restored the original full?  The differential backup is a subset of a full backup so a full backup must  first be restored.

We see the server is "Legato Networker Server Version: NetWorker 7.2.1.Build.311 Enterprise Edition ".
Client is "nsrexecd.exe Version: 7.3.2.Build.364".
Our SQL module is "nsrsqlrc.exe Version: 5.1.1.202 Supporting SQL 7.0, SQL 2000, and SQL 2005"

This is the important part where the full is not present for the differential to be restored against.

38006 9/10/2010 12:10:40 AM  5 0 0 5800 11280 0 SQLSERVER_A nsrsqlrc This differential backup cannot be restored because the database has not been restored to the correct earlier state..
38006 9/10/2010 12:10:40 AM  5 0 0 5800 11280 0 SQLSERVER_A nsrsqlrc RESTORE DATABASE is terminating abnormally..
37708 9/10/2010 12:10:40 AM  5 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc nsrsqlado.cpp(2328): ExecuteFailed event arrived.
35867 9/10/2010 12:10:40 AM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc Error processing SQL database 'wss_database'

Please not that we do not recommend that the client version be higher than the server version.

Thanks for your reply

Here is the log. Looking at the log it appears that full restore of databse completed and terminates with error while recovering differential part of restore.

37983 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc Legato Networker Server Version: NetWorker 7.2.1.Build.311 Enterprise Edition
52708 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc nsrexecd.exe Version: 7.3.2.Build.364 
52708 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc nsrsqlrc.exe Version: 5.1.1.202 Supporting SQL 7.0, SQL 2000, and SQL 2005
43337 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc Command line:
43338 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc   nsrsqlrc -s BACKUPSERVER -c SQLSERVER_B -d MSSQL: -I - 
37693 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc SQL Connection to SQLSERVER_A is created. SQL Server Version is 09.00.4035
52757 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc Command line -I item:   -d "MSSQL:wss_database_20Aug_tmp" -C " 'wss_database'='E:\MSSQL2005\MSSQL\wss_database_data_20Aug_tmp.mdf', 'wss_database_log'='J:\MSSQL2005\wss_database_log_20Aug_tmp.LDF'" -t "Fri Aug 20 17:19:21 2010" "MSSQL:wss_database"
37725 9/9/2010 4:31:41 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc Recovering database 'wss_database' into 'wss_database_20Aug_tmp' ...
37944 9/9/2010 4:31:42 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc bsGetOrigLFiles: directory object name is MSSQL:/wss_database%/files.1280599372.1280599407
29395 9/9/2010 4:31:43 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc bsGetOpaqueList: returns success.
4690 9/9/2010 4:31:43 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc RESTORE database [wss_database_20Aug_tmp] FROM virtual_device='Legato#744383f4-fb09-49d7-ace9-849eed8fbab0'  WITH move 'wss_database' to 'E:\MSSQL2005\MSSQL\wss_database_data_20Aug_tmp.mdf', move 'wss_database_log' to 'J:\MSSQL2005\wss_database_log_20Aug_tmp.LDF', norecovery
35866 9/9/2010 11:41:40 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc The restore of database 'wss_database' completed successfully.
37944 9/9/2010 11:41:40 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc bsGetOrigLFiles: directory object name is MSSQL:/wss_database%/files.1282339161.1282339188
29395 9/9/2010 11:41:57 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc bsGetOpaqueList: returns success.
37751 9/9/2010 11:41:57 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc RESTORE database [wss_database_20Aug_tmp] from virtual_device='Legato#493bc10e-8d2f-49ed-8954-a75cc1bc88bc'    (differential)
29085 9/10/2010 12:10:40 AM  5 0 0 5800 11280 0 SQLSERVER_A nsrsqlrc Microsoft SQL Server Provider error:
38006 9/10/2010 12:10:40 AM  5 0 0 5800 11280 0 SQLSERVER_A nsrsqlrc This differential backup cannot be restored because the database has not been restored to the correct earlier state..
38006 9/10/2010 12:10:40 AM  5 0 0 5800 11280 0 SQLSERVER_A nsrsqlrc RESTORE DATABASE is terminating abnormally..
37708 9/10/2010 12:10:40 AM  5 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc nsrsqlado.cpp(2328): ExecuteFailed event arrived.
35867 9/10/2010 12:10:40 AM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc Error processing SQL database 'wss_database'

Please note that 7.2.1 NetWorker is at EOL.

The first thing we need to clarify is that the correct full is matched to the correct differential. 

Thanks for your analysis

But there is a line which tell that database restore completed successfully before differential.

Or do you mean that the attempted full database backup/differnetial combination was wrong? (for eg if the recent full backup metatdata was lost)

35866 9/9/2010 11:41:40 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc The restore of database 'wss_database' completed successfully.
37944 9/9/2010 11:41:40 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc bsGetOrigLFiles: directory object name is MSSQL:/wss_database%/files.1282339161.1282339188
29395 9/9/2010 11:41:57 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc bsGetOpaqueList: returns success.

37751 9/9/2010 11:41:57 PM  1 0 0 10920 11280 0 SQLSERVER_A nsrsqlrc RESTORE database [wss_database_20Aug_tmp] from virtual_device='Legato#493bc10e-8d2f-49ed-8954-a75cc1bc88bc'    (differential)

Yes, I am running an unsupported version , but the isuse is not particualr to 7.2.