Have you checked the maint plan history to see where the failure occured and what may have been successful? I have found that it is very helpful on telling you what went wrong, which for me was usually a wrong setting. Try this article to see if it will help.

http://support.microsoft.com/default.aspx?scid=kb;en-us;288577