Debian :: Running Synaptic - No Version Information Available

I have installed Openshot Video editor, then it did not work (due to some python bindings I guess) so I uninstalled it. After that everything seems to start failing including, running aptitude and apt-get. Here is a message when I try to run apt-get from command line (sudo apt-get install -f)

Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 11 not upgraded.
1 not fully installed or removed.
After this operation, 0B of additional disk space will be used.
Setting up shared-mime-info (0.71-3) .....

Here is I am trying to run synaptic from command line:
synaptic: /usr/local/lib/libz.so.1: no version information available (required by /usr/lib/libxml2.so.2)
/usr/bin/python: /usr/local/lib/libz.so.1: no version information available (required by /usr/bin/python)
/usr/bin/python: /usr/local/lib/libz.so.1: no version information available (required by /usr/bin/python)
synaptic: symbol lookup error: /usr/lib/libxml2.so.2: undefined symbol: gzopen64

This is from "/usr/lib$ ls libz* -al"
-rw-r--r-- 1 root root 90284 Dec 28 2009 libz.a
lrwxrwxrwx 1 root root 16 Jun 29 23:18 libzbar.so.0 -> libzbar.so.0.2.0
-rw-r--r-- 1 root root 183284 Jun 9 11:13 libzbar.so.0.2.0
lrwxrwxrwx 1 root root 18 Jun 15 21:13 libzephyr.so.4 -> libzephyr.so.4.0.0
-rw-r--r-- 1 root root 51396 Nov 29 2009 libzephyr.so.4.0.0
lrwxrwxrwx 1 root root 15 Jun 16 20:40 libz.so -> libz.so.1.2.3.4
lrwxrwxrwx 1 root root 15 Jun 15 20:27 libz.so.1 -> libz.so.1.2.3.4
-rw-r--r-- 1 root root 79980 Dec 28 2009 libz.so.1.2.3.4