Yup, multiplayer is most troublesome. Even when the game was new, it was pretty glitchy. If you look at the bottom of the first post in Salbei's
Custom Version Thread he has some great info on multiplayer, how to get it working, and what
not to do to make it crash. It seems that some of the largest culprits are any cards that allow one to search a library (such as
Flooded Strand). There is so much stuff being worked on in front of Multiplayer (and Shandalar) that it'll most likely be a long time before any of the current developers will have a chance to take a good look at the issues with either of them.
Try following the steps in Salbei's thread and avoid using cards that search libraries. There's a
previous thread discussing the issues with Multiplayer that is well worth reading. Although it's an old thread it's still very relavent, as no changes have been made to Multiplayer (but new bugs may have been introduced).