Hi Dimitri,
I have this working here. With automatic labeling. When you submit the jobs, which messeges do you see for the jobs in the "status dir" command from bconsole? Usually the messeges there tell us something about why the jobs did not start concurrently and what for is the second job waiting.
Just for checking: have you enabled the storage concurrency both on bacula-sd.conf and bacula-dir.conf?
Best regards,
Ana