I still received this error after installing the critical update for SQL 2005 SP2. I found another article from MS that suggested running the below script, after running it the Maintenance Plan ran without errors:
sp_configure 'allow updates', 0
reconfigure with override