You say you are using 3g/2g to use Skype, my bet is that your carrier has started blocking the ports it uses.

Try Skype over wifi like assetburned mentioned.

I'm also having no problem with skype over any connection type.