Just finishing my buffer based ledmatrix library, I ran into this problem while developing the library -- it turns out that sending in right commands in right sequence is important. If commands are not right, or they are not clocked right (raise and lower the CS/LOAD pin), the Max7219 gets into weird states and will behave strangly -- sometimes all leds are turned on, sometimes only a few, sometimes ... well you probably have seen it already.
My solution is to power everything down when it happens, detach the led matrix from Arduino, fix the code to get it right, then reconnect and power up. After I got the commands/data clocked into 7219 correctly, I do not have this issue anymore -- still, sometimes all leds are on, but will shutdown correctly.
Another way to test your Max7219 is to use a well known library (mine is too new :-)), like LedControl to test it.