Check the "Automatically set I/O affinity mask for all processors" in your server properties. We had unselected this to reduce processors for licensing, and the maintenance plan failed the following weekend and since. I reselected thsi and the plan started working. Still sounds like a bug Microsoft should fix as a plan shouldn't fail for this reason.