Maria - I accumulate such tips in my ADSM functional directory,
        at http://people.bu.edu/rbs.

You say that you have "collocation turned on" - but what kind?
Collocation by node is insufficient for your purposes.
From my tips:

Parallelize backups                     Going to a disk pool first is one way;
                                        then the data migrates to tape.
                                        To go directly to tape: You may need to
                                        define your STGpool with
                                        COLlocation=FILespace to achieve such
                                        results; else *SM will try to fill one
                                        tape at a time, making all other
                                        processes wait for access to the tape.
  Richard Sims, BU