It might be broken.
Buying a new sensor board with a broken HMC5883L on it, is something I never heard of. It is always some kind of other problem.
I can think of two things:
(1)
In some cases the I2C-bus needs a level shifter :
http://playground.arduino.cc/Main/I2CBi-directionalLevelShifterUsing a 3.3V I2C-bus with a 5V Arduino is living on the edge as you can read in that link.
(2)
It could be bad soldering.
Carefully check each soldering with a magnifier (or make a photo of it). You must see that at each connection the solder has flown. If you spot a problem, soldering might be too tiny, but you could use a heat gun to try to make the solder flow.
If this doesn't help, buy a new one. Preferably at Sparkfun or Adafruit, or a cheap one on Ebay.