You can solve the issue by added set layers to your axis. This activates layered graphics for your tikzpicture, and the layers are drawn in the correct sequence. The default is to the single axes individually, which can cause the observed effect. Setting set layers should not have any negative effect on the appearance and the small additional runtime cost is probably irrelevant.
The feature set layers is relatively new and requires pgfplots 1.7
Perhaps this should become the default eventually...
Best Answer
You can use the
grid style
option (for each grid line), ormajor grid style
(for each major grid line):