Did you get anywhere on this or come up with a workaround?
I have the very same issue.
I changed some of my a4j:commandButtons to h:commandButton to get a full page refresh (including working queues), because these buttons already did an almost complete page refresh with ajax. The h:commandButton does of course always work, even if the a4j queue is blocked.
I also found that the a4j queue can be blocked if the user clicks an ajax-enabled element while the page is still loading. I cannot reproduce this, however, sometimes the first click during page load is just swallowed and further clicks work as expected.
So it's not even a workaround.
Anyone else experiencing blocked queues (even if the server already responded)?