What are some concrete steps to deal with the vanishing gradient problem? I am training an ANN for classification between 3 classes. The ANN has an input layer, one hidden layer and a 3 node output layer. 

The problem I am facing is that the output being produced by the 3 output nodes are so close to 1 (for the first few iterations at least, and so I am assuming the problem propagates to future outputs as well) the weights are not being updated (or hardly updated) due to overflow (about $10^{-11}$). I can fix the overflow problem (but I don't think it is the culprit). I think such low values of error is the main culprit, and I cannot figure what is causing such low values of error. 

What will cause the network to behave more responsively, that is, how will I be actually able to grasp the weight updates and not something in the order of $10^{-11}$?

The data set contain values in the order of $10$'s, and the weights randomly initialized are in the order of $0 &lt; w &lt; 1$. I have tried feature normalization but it is not that effective.
There is not single answer to the vanishing gradient problem. However, there a few things that can help.

As mentioned in the comments, use of Rectified Linear Units (ReLU) as your activation function can help, since the it does not get saturated for large neuron inputs.

Next, careful choice of weight initialization can help avoid saturation, as well. See Andre Ng's Coursera video for details.

Finally, if you are concerned that the scale of your training input is causing issues with training, you can normalize the training examples by subtracting the mean and dividing by the standard deviation. There is a normality assumption here, but this can often help avoid problems where one feature is far out of scale with another. However, this usually causes issues with optimization bouncing between the walls of long, thin trough, which complicates convergence, but does not cause vanishing gradient.