I was having this problem as well on a potato machine. I never found out what the problem was, but it somehow fixed itself. I don't think it had anything directly to do with apt-get or dpkg, but perhaps a bug in libc? Do an apt-get dist-updgrade and then play around with it again. One thing I started messing with in the interim was console-apt. I don't know if it did something to correct the problem. If so, then perhaps it was a problem with the database????