The example 'hello_matrix' from the arduino ide uses as a default digital pin 0, 1, 2 for the communication with the MAX7219. That is frustrating, because it is not working with an Arduino Duemilanove. I think its because pin 0, 1 is used for RX, TX. I spend a lot of time finding the error. The next morning, with a refreshed mind, I used pins 2, 3, 4 - and it worked like a charme. Maybe you should change the example to use other pins than 0, 1, 2.
Regards,
Christian