Hi Chris,
There are some users who've been experiencing a problem getting onto Gamespy's match making service. While modifying the CD key in the registry in various ways has helped some customers there are still some who it doesn't work for. We are currently investigating what may be causing this but it's difficult to allocate the resources given the developer's current priorities what with Empire: Total War and Stormrise both coming out in the next few months.
We'll let you know as soon as we have more information. As for the issue affecting 1.3 and not 1.2, 1.3 is part of Kingdoms, so you would have to install just Medieval 2 from the first disc and not the expansion from the second disc to test this theory.
Best Regards,
Frank