Looking at the code linked, the font is storing "byte"s in program memory, you can't do that and when you read it back you'll get a garbled result pretty much exactly as you describe. Read the documentation here: PROGMEM - Arduino Reference
I would also suggest you look at the LedControl library for the MAX7219.
I have mine set up on a breadboard while I'm waiting for PCBs to arrive, and it's working perfectly. The MAX7219 only scans the display at 800Hz, so I can't imagine any sort of "high frequency" problems.