If you're using Vista, make sure that your Microphone you plugged in is set to the default recording device.
I know mine was originally set to the PC's sound itself, until I had to play around with the settings.
If your PC's sound, is set to the original device and your mic plugged in is set to it on MSN, it may be causing conflict and thus not working.

Just a thought.