It could well be your firewall - chances are your firewall is stopping skype on your computer communicating with its home world;) What firewall have you got? If its zonealarm like me, or norton or similar it will be running in the background always and you may have inadvertly turned off the option which asks you if you want to let it through.
However, it should be in the bottom right in the system tray (next to clock) load it up and find the option that is blocking it - OR - just to check disable your firewall and then try skype
It is also possible you have windows XP firewall running (if you don't have your own firewall program) - see here to modify this -> http://www.microsoft.com/windowsxp/using/security/internet/sp2_wfintro.mspx
Alternativly, as you have MSN, make sure you have the latest and use that to make video/audio calls as I actually find it more stable than skype - but it is dependant upon your connection etc. so good to try both if you can:)
Mail me if you need any help with doing any of that - be good to give you some advice for a change;)
The shame I am such a geek:(!!!!