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

small database.

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.