$L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?
If a queue automaton is Turing-Complete, then it can compute (decide) any function (language) that a Turing machine can. And we know that TM can decide both $L = \{x\#x^R \mid x\in\{0,1\}^* \}$ and $L = \{x\#x \mid x\in\{0,1\}^* \}$, thus both can be decided by a queue-automaton.

"How?" you ask? For this you need to understand how a queue-automaton works. It starts with the input already in the queue (where the end of the input is marked by a special character $\$$), and then at every move it reads the letter at the head of the queue and can insert one or more characters to the end of the queue.

Let $M$ be a TM. The way to simulate $M$ over the queue automaton is to keep reading content out of the queue and then putting it back into the end of the queue. This allows us to make multiple passes over the "tape" of the TM. For instance, assume the queue holds "abc$". A "Cycle" (a pass on the queue) will look like (plotting the queue content):

 abc$ -&gt; bc$a -&gt; c$ab -&gt; $abc -&gt; abc$


and we are back to square one, allowing the machine now to take another pass on the input. 

It is then trivial to simulate the TM moves as long the head moves to the right, or stays in place: we can denote the heads place by a special symbol ($\to$) that points on where the TM head looks at. E.g., at the very first move we do:

abc&amp; -&gt; bc$→a -&gt; c&amp;→ab -&gt; ... -&gt; →abc$


Then moving the head to the right is elementary: 

→abc&amp; -&gt; abc$ -&gt; bc&amp;a→ -&gt; ... -&gt; a→bc$


It is a bit more tricky to simulate a move of the TM head to the left, because seemingly, we need to put the head even before we see the next letter that causes the move back.

The trick here is to use the current state in order to "keep one letter in the memory". So when we see a letter, we don't immediately put it back to the queue, but we "remember" it using a state (e.g. if the states of the TM are $q_1,q_2,..$ etc, we will move to $q_1^a$ if we see an a or to $q_1^c$ if we see a c, etc.) 
Before putting the letter back to the queue we first we check the next letter, and if it is not the head, we put it back, If it is the head, we may move the head as needed.

The cycle of moving the head left will look something like the following:

a→bc$ -&gt;(remember a using states)-&gt; →bc$a -&gt; bc&amp; -&gt; (*)


at this point the machine knows it needs to move the head to the left. It remembers a and so it put it back in the queue, now remembering b using the current state 

-&gt; c$→a -&gt; $→ab -&gt; ... -&gt; →abc$