I recently had a problem with cydia crashing and searched for the error and fixed it. The fix was deleting the /var/lib/dpkg/updates folder. I launched cydia and I got this error when installing something. "dkpg: cannot scan updates folder /var/lib/dpkg/updates no such file or directory" so I did the obvious thing- I created a new updates folder. I still got the error. I also tried setting the permissions to read/write/execute for all groups. Still no luck
I too was frustrated with a dpkg error for countless hours until I realized what my problem was. I had used the iPhoneBrowser to use the iPhone as a USB Drive...basically sore non iphone files on some of the hard drive space I had free.
I had plenty of space free but the real problem is the iPhone actually splits the hard drive into two partitions (one is very small, which is like 750mb) and little did I know that's where I had put my 3rd party files.
Some but not all cydia installs / updates seem to install on the smaller partition..so long story short if you did upload any files on the iphone or create new directories to use it as storage delete them (you can host it on the bigger partition but i forget the directory off hand).
if you understand how cydia works it uses dpkg to figure out where packages are located and how to interact with such. since you do not have the ability to install packages via cydia you will need to find a way to reinstall dpkg. unfortunately because you cannot use dpkg properly you will be unable to install any .deb. you /could/ install dpkg manually but for a more simple approach you can run redsn0w again to install the default packages.
you might just consider restoring because i am not really sure whether reinstalling everything will go as smoothly as in theory.