I'm actually just about to start a similar project to convert an old organ console into a MIDI controller for my computer. Magician is right; you have two problems to tackle here: the (hardware) controller and the synthesis. Disclaimer: I'm also a complete newbie to Arduino, but I've done a fair bit of programming and I'm currently studying audio engineering.
Outputting MIDI via USB on the Arduino itself seems perfectly plausible, and also more sensible than wasting serial pins when you're already gifted with USB output 
That SpikenzieLabs link looks like it could already have it sorted for you...
There is a library that reads switch matrices here: Arduino Playground - Keypad Library and it comes with its own tutorial: Arduino Playground - KeypadTutorial. It may need a little modification to handle large matrices (I need to read in 200 odd switch inputs!) but it looks like a very good start. The Arduino MIDI libraries look like they can handle all the MIDI output needs you'd ever want, so all you'd need to write is some code to map the output returned by the Keypad library into input for the MIDI library. The Keypad library has both key press and key release handling which you'd use to send your note-on and note-off messages. Handily, there's a built in event listener, which you'd probably want to use to call your own code.
Let me know how you get on; if I come up with anything handy, I'll be sure to stick it up on the Playground.