First off, try re-installing your VC. If you have already, do it again since I want this to flow strictly on my wave. Then, download the latest client (0.3zR2) from the Multiplayer site (vicecitymultiplayer.com)
Pick a folder which you can remember to find later on for your regular Vice City directory. Indicate, in the MULTIPLAYER installer, that same directory so all the files from the Multiplayer installer can extract into that directory.
Once you're done, find the directory in which both components (Vice City and VC:MP) should lie. There you'll find vc-mp.exe. Right click it and select "Run As Administrator". This has helped me in many cases on VC:MP so I think it should help you too. 
btw:// If the game's on it's regular CD and not off Steam, then it'll contain the 1.0 exe. Don't worry about people confusing you with the vc.exe versions.