I don't think you're going to be able to use the MAX7219; with common cathodes on your LEDs you would need the 7219s to be in sync with each other (so that each was selecting the same DIGx pin at the same time), and I don't know if that's possible.
You might want to look at the schematic of this product for ideas:
-- http://www.sparkfun.com/commerce/product_info.php?products_id=760#