MSDB Restored, Version of SQL is same, But failes to run Maintenace plan

Please set the sys subsytem values to proper values.

Example :-

use msdb
go
select * from msdb.dbo.syssubsystems


update syssubsystems set subsystem_dll ='E:\Program Files\Microsoft SQL Server\MSSQL10_50.MSSQLSERVER\MSSQL\binn\SQLCMDSS.DLL'
where subsystem='CmdExec'


Restart SQL Agent once Done.

Table with values you can find here :- http://support.microsoft.com/?kbid=903205

Map the dll with your DLL file location, It must work