Can you post the results to the following:
SELECT * FROM msdb.dbo.sysdbmaintplan_history
This will give you a much greater detailed message as to why the job is failing.
Chris Powell
George: You're kidding.
Elroy: Nope.
George: Then lie to me and say you're kidding.