I had similar problem on a dataset where the number of samples was just x10 the number of parameters. Data was noisy and optimization would get stuck producing good results only for the frequent samples. Decreasing the batch size helped as it allowed the optimizer to better explore parameters for the less-frequent samples as well.
I got good results with batches of size 1-2. This significantly increased duration of a single epoch, but I could reduce the number of iterations and arrive at much better solution than in the past.