Are there particular datasets where neural networks cannot converge well on?

Backpropagation is another name for (stochastic) gradient descent-based optimization, and gradient methods are known to be very robust and generally converge to a local minimum is the learning rate is set to a good value (so set an unreasonably high learning rate and watch almost every neural network trash and suffer when learning almost any dataset). Very deep neural networks, also tend to converge to very bad local minima if trained discriminatively with first-order gradient descent, but this can be circumvented by unsupervised pre-training and/or higher-order optimization methods. Another thing thatm ight interest you is that without proper complexity control neural networks can overfit badly on datasets with a significant amount of either feature or label noise. To see this pick almost any real-world dataset that is not very large and train a neural network directly minimizing squared/logistic loss on training data without early stopping or regularization, and see that as the training error goes to zero the test error gets really big. Another possibility is, as Justin suggested, picking irrelevant features or an unsoluble problem, like training a neural network to reverse RSA ecnryption or something like that (although probably in some of these unrealistic datasets you'll still get somewhat ok training error if you tune things long enough).

But neural networks are usually reliable and gradient descent has very nice properties, so I don't think you'll ever see a natural dataset where there is actual lack of convergence.

Neural Networks are universal approximators in a sense that they can fit any dataset arbitrarily well. There's an issue of back-propagation being stuck in suboptimal local minima, but as you increase the number of elements in hidden layer you get stuck less often. In the extreme example, with infinite number of hidden layers, optimization surface has unique local minimum. This is the idea behind "convex neural networks".

Therefore, examples of neural network failures to fit training data have to be architecture specific. Classical example is the XOR dataset, take network with 2 input units, 0 hidden units, 1 output unit and the dataset

1,1 labeled 0
1,0 labeled 1
0,1 labeled 1
0,0 labeled 0

I don't think such a database would make sense. Since you can make up trivial examples of where neural networks would have difficulties, e.g. predict the brand of a car given a 1024x768 image.

Much more interesting are datasets which illustrate the "edge". Where learning algorithms are able to do something, but not everything. A tough dataset like that is CIFAR-100, for example.

I think that there has to be "something" that indicates that a dataset is actually "learnable", that there is enough structure in it but that NNs somehow fail to find.

If a neural network does "terrible on a training set", (assuming you are using enough nodes, layers, proper learning rate, etc.). It's not really the neural networks fault because it can always provide you with a network that simply gives you a one to one match of the training input and training output. You are just using crappy training data ( garbage in, garbage out) and no algorithm will fix that.

Alexandre and Justin and ukurokawa touched on this already but the main issue with neural networks is over training and sparse data. Specifically, if you have very sparse data then running the training repeatedly over the data is more likely to overfit then neural network and make it less applicable when presented with new data. However, if you have a lot of unique data, or data that covers all possible kinds of data that will be seen, then you can train a neural network on fewer iterations and therefore with lest overfitting.

traditional multilayer perceptron on two spiral problem without additional information.