When overclocking I usually don't overclock the GPU memory as it really doesn't show a big difference, I only overclock the core clock as that jumps my hash rate up significantly. I have 2 x R9 390 one OC to 1175MHz core clock, getting me 33Mh/s, and the other at 1120MHz, 32Mh/s. Both give me 65Mh/s, that's without touching the memory speed, leaving it at 1500MHz.
Hope this helps with getting better speed.