The particular update you are referring to dealt with Servicing Stacks and some network DLLs were changed.
That may be what is upsetting your Skype, but that is difficult to say with certitude.
I'm not sure why you removed other updates - but its unlikely you can remove the cumulative update unless you do a System Restore and roll back your System to a date prior to the update. That will not help ultimately given this critical update will simply download and install again sooner rather than later.
The simplest thing probably is to reinstall Skype using their msi file:
http://download.skype.com/msi/SkypeSetup_7.25.0.106.msi
With a reinstallation as it sets up and connects you may find any current issues are resolved during the installation process.