You could try a couple of other things like:
1. Have a look at your maintenace plan, click edit on the subplan and click on view t-sql. Any problems there?
2. Delete your maintenance plan and just create a new one, this has worked for my on a couple of occasions.
3. Create a new maintenance plan that does what your original plan, point it to another folder and test it for one
Is your instance RTM version? Maybe there is a SP or CU that will solve this, always seems to be some problems with
maintenance plans and early versions of SQL Server.
I would recommend you to have a look at Ola Hallengrens maintenance solution http://ola.hallengren.com
It is a great solution for backups and mainteance that has made my life much easier. Spend a couple of hours testing
it and I assure you that you will start using it instead of the built in maintenance plans.