1. Run Cydia.
2. Search for gzip & reinstall.
3. Search for bzip2 & reinstall.
4. Cydia goto Changes & click Refresh.
5. Wait for Cydia to refresh.
Not sure if you came across this on the net as well..
Solution:
1- Get your way to the file and directory structure of your iPhone (through SSH or iFile or Mobile Terminal ...)
2- Look for the /var/lib/dpkg/ directory
3- You should be able to find the following files: available, availble-old, status, status-old
4- Rename "available" to "available-bak"
5- Rename "status" to "status-bak"
6- Rename "available-old" to "available"
7- Rename "status-old" to "status"
8- Start Cydia , make sure that you allow Cydia to load completely first (just to be on the safe side ), try to install some apps.