I just uninstalled and reinstalled Cydia using SSH and Mobile Terminal. I was having some slightly flaky Cydia behavior but not as bad as failing to install packages. Unfortunately it didn't change the flakiness. But if you want to try, the procedure I used is described at this link:
http://www.ipodtouchfans.com/forums/showthread.php?t=288899
Basically the procedure is as follows:
On your computer, download the following .deb files (or check apt.saurik.com for later ones):
essential_0-1_iphoneos-arm.deb
cydia_1.0.3222-73_iphoneos-arm.deb
For convenience, shorten the names to "
essential" and "
cydia" (no extensions).
Using SSH or some other method, get the files into the folder
/var/stash on your i-device.
Using Mobile Terminal or an SSH terminal, enter the following commands on your i-device:
su
alpine [or your own root password]
apt-get remove cydia [at this point it will complain bitterly and ask you to enter "Yes, do as I say!"]
Yes, do as I say!
cd /var/stash
dpkg -i essential cydia [or whatever names you gave the two deb files; hopefully this step will succeed!]
Then respring or reboot your i-device.
(Warning: removing Cydia is risky because if you can't reinstall it you will have to restore and re-jailbreak)
If you need Mobile Terminal, a beta that works with iOS4.x is available at this repository:
http://www.podzombie.com/repository/