Hi Andy,
It's not surprising that Maya is doing it too. This is not a problem with Qube or C4D or Maya... It's a problem with something else on your network. Something is causing access to the file server to be inconsistent. It may be your AD/LDAP server (if you have one), it may be a failing/flooded switch, it may be the file server itself (maybe it has a limited number of allowable connections? Maybe its disk is failing? Maybe it doesn't have a good connection with AD/LDAP/NIS?).
I won't be able to help you solve the problem, but I can help you work around it.
In the submission dialog(s), towards the bottom, with "Expert Mode" turned on, there are two fields that are important: "Retry Frame/Instance" and "Retry Work Delay". The former tells Qube how many times to try the frame before it gives up on it. For example, setting it to 5 means "allow each frame to fail 5 times before moving on".
The latter tells Qube how long to wait between each retry. This field is *essential* in your case & was introduced to combat this very issue. As your testing has shown, this problem clears itself up eventually. Without a delay between retries, Qube can blow through its retry attempts in a matter of a second or two. Telling Qube to wait between retries gives the file server (or switch or AD server, etc) time to recover from its problem.
You'll probably want to experiment with values for these fields. I would suggest 5 and 15, respectively, as a starting point. YMMV.
I'm sure I don't need to tell you this, but so it's said, we are working *around* a problem, not fixing it. You'll want to find out what's causing this behavior as it's likely not going to get better on its own.