Several fundamental questions about CNN
Here's my take on each of your points.


You have very sparse data. Are you storing these data optimally in a sparse object, for example a csr sparse matrix if you're using Keras? This is more likely to affect training time than accuracy, but is something to think about.
5000 training examples and 500 testing examples sounds alright to me, except you may have too few data to fit the type of model you have (you may be severely underfitting). Try a simpler model and see if you can improve results with that (try something stupidly simple like an MLP with one layer and see what happens).
This seems the most likely problem. My first guess is this has to do with the unbalanced classes. If you're using a metric like accuracy to evaluate training at each epoch, I'd recommend instead using something like average_precision or roc_auc_score or f1, all available through scikit-learn. If you're  using Keras, try using class_weights as well, which will weight underrepresented classes higher in the loss function, essentially biasing the algorithm to consider underrepresented classes on an equal playing field. If you're not using Keras, try implementing some similar class weighting scheme.
Batch normalization is less popular now than it used to be. It's worth trying the architecture with and without batch normalization to see if it provides a clear benefit.
Yes, if your data are purely random then you will not detect a signal at all. This goes back to point number 2 (try a simpler model and see if you can detect a pattern). You can also try visualizing some of your samples to see if you can visually see a difference between the classes.


With regard to Xavier initialization, I don't think that's the likely cause of the effect you're seeing. The type of initialization can affect results, of course, but from what you're describing, I strongly suspect this is due to too little signal from the data or the unbalanced classes problem. 

Hope that helps!