I can say pretty confidently that the problem is not in aptitude if apt-get also crashes (and if, as your backtraces show, the crash is in database code). I can't think of any reason offhand that this should happen, but I'll redirect you to the apt authors.
Just to rule this out, have you tried running a memory tester on your laptop? Daniel
signature.asc
Description: Digital signature
