Ive not experienced your problem, except in relation to the version of the DirectX SDK that I am using.
The GDK's multiplayer.lib is using a DirectX library that is no longer included with the DirectX SDK after the August 2007 version. As Bran flakes91093 said, you can find how to make a dummy multiplayer.lib to work around that problem by searching the forums, its quite easy to do, I use a dummy multiplayer library myself as I use the latest DirectX SDK's as they are released and its not hard to find networking libraries you can integrate easily in its place.
But, if you are using the August07 DXSDK the deprecated library will not be your problem. You said that you un-installed and re-installed everything, I do know from experience that the order in which you install GDK and the DXSDK can make a difference as to whether the installer does what its meant to.
If you could post your code aswell, and the errors you are getting, it might help someone narrow the problem down for you
good luck
If it ain't broke.... DONT FIX IT !!!