I'd suggest that any network using sigmoid-like limiting functions at the nodes can be mapped in an almost infinite number of ways to binary, using a threshold (sign) or a pair of thresholds (binary classification with hysteresis, for time varying data; or a trinary output, with an "unknown" or confusion state). With many of the NN I worked with, I included "not-possible patterns" trained to a midpoint level. This sometimes helped produce a better generalization in the final result.

May be the trouble is the topology of the NN. How many layers? how many neurons per layer?

Training data is "very close to random"? I doubt that you can make up in the discriminant function a problem that lies in the measures. If there is no information, than there is little to learn.

It may be the data as Monther and others have said. I'd agree with James on trying a sigmoid for binary classification problems in which case you can use the backpropagation algorithm or other gradient descent variant for training. You can use tanh() for +1,-1. If you try this, you'll find it's important to match the learning rate (which affects the update step size) to the number of neurons plus the ability to generalise will depend on topology e.g. number of neurons in hidden layer(s), as Glen also mentioned (for example you can have too many hidden neurons versus the number of classes you are expecting). There are heuristics for optimising many of these choices. I discussed a few of these in one (although rather old) paper http://eprints.nottingham.ac.uk/1901/ which is also on RG. This focusses on convergence but is also relevant to generalisability.