Hi,
First, if you run Network cleanup it will affect only network related/shared database tables. To cleanup individual sites tables, plugin needs to be used with each site independently. Plan is to have network control cleanup affecting all sites at once, but that is planned for version 5.0 and no timeframe for that release exists yet.
As for your problem, cleanup mostly didn’t even start due to the error, either in JavaScript or on server side. Can you list exactly which tools for cleanup you checked for use? Also, when you start the process, check out if there are any JavaScript errors in the browser (Firebug for Firefox debugger or similar). And check out server error log for any errors in PHP logged there.
Milan