Why does changing one bit in a Triple DES key or i

I'm using pyDes to encrypt some data. I wanted to demonstrate that if you change even one bit in the key or initial value, the encrypted data would be totally different. I set up the 16-byte key to change the last character by +/- 1, causing at least one bit to be different. However, even when I do that, the 3 different instances of encrypted data are not all different.

from pyDes import *

data = 'Hello'

# CBC : Cipher-Block-Chaining
# \0..\1: arbitrary initial value for CBC
# pad=None: let pyDes take care of padding bytes
k1 = triple_des("16-byte-key-here", CBC, "\0\0\0\0\0\0\0\1", pad=None, padmode=PAD_PKCS5)
k2 = triple_des("16-byte-key-herf", CBC, "\0\0\0\0\0\0\0\1", pad=None, padmode=PAD_PKCS5)
k3 = triple_des("16-byte-key-herd", CBC, "\0\0\0\0\0\0\0\1", pad=None, padmode=PAD_PKCS5)

d1 = k1.encrypt(data)
d2 = k2.encrypt(data)
d3 = k3.encrypt(data)

assert d1 != d2
assert d2 != d3
assert d1 != d3

One of the assertions seems to fail if I only make a small change to either the key or initial value; I have seen both d1 != d2 and d1 != d3 fail depending on what I change. I have also tried changing 'Hello' to 'Hello' * 50 to make sure it wasn't just a case of the input data being too short.

If I make totally random keys, the assertions pass. With the program as seen above, d1 != d3 fails (those keys are one bit apart; k1-k2 are 2 bits different).

I am by no means an encryption expert, but if two keys only one bit apart result in the same encrypted data, then that means the effort it takes to brute-force the key just went down by a factor of two, right?

Am I missing something obvious? Is Triple DES not supposed to give unique results for very similar keys? Or is this a bug in PyDes? Maybe someone else could confirm this behavior in another implementation?

@Chris Jester-Young had the answer that some of the bits in the key are parity bits. And as it turns out, according to this article:

Note that although the input key for DES is 64 bits long, the actual key used by DES is only 56 bits in length. The least significant (right-most) bit in each byte is a parity bit, and should be set so that there are always an odd number of 1s in every byte. These parity bits are ignored, so only the seven most significant bits of each byte are used, resulting in a key length of 56 bits. This means that the effective key strength for Triple DES is actually 168 bits because each of the three keys contains 8 parity bits that are not used during the encryption process.

(emphasis was mine)

And those parity bits were exactly the bits I was changing in the example.

Thanks Chris!

In DES, some bits of the key are parity bits, and don't actually affect the encryption/decryption.