Are ReLUs incapable of solving certain problems?
There are a variety of possible things that could be wrong, but let me give you some potentially useful information.
Neural networks with ReLU activation functions are Turing complete for a computation with on order as many steps as the network contains nodes - for a recurrent network (an RNN), that means the same level of turing completeness as any finite computer. In other words, for any function/algorithm that you want to compute, you can devise a neural network, potentially recurrent, that will approximate/compute it.
As an example, suppose that we want to compute the NOR function, which can be used to implement a Turing machine.  We can do it with the following neural network with a ReLU activation function.
Let the input be
$$ W = \begin{bmatrix}x_1 \ \ x_2 \end{bmatrix}$$
the weight matrix be
$$ W = \begin{bmatrix} -20 \\ -20 \end{bmatrix}$$
and the bias be
$$ b = \begin{bmatrix} 1 \end{bmatrix}$$
Then the ReLU unit (or neuron) performs the following operation
$$o = \max(Wx + b, 0)$$
So, $o = 1$ only when both $x_1$ and $x_2$ are $0$, otherwise, it's always $0$.
However, gradient descent is a finicky way to search for RNNs. There are a wide variety of ways that it might have been failing. In general, once you have very thoroughly checked your gradient, I'd make sure to use Adam as the optimizer and then play with the hyperparameters endlessly until I find an incantation that works.
For further reading on general understanding of this level of deep learning's capability limitations, I'd recommend this blog post by Ilya Sutskever, now an OpenAI researcher: http://yyue.blogspot.com/2015/01/a-brief-overview-of-deep-learning.html?m=1