Maintenance Plan fails but the query it generates Runs
The SQL Server Agent account has both share and local security permissions right?

I would also ensure that you have given the SQL Server Agent appropriate network permissions -- it really sounds like a permission issue.