無意識にこの罠にハマったので、残しておく。
リストの一部を変更したのに、すべてが変更されてしまう場合はだいたいこれ。

掛け算オペレータでリストを初期化

Python のリストを初期化する際、すべての要素が同じでよければ、下記のように掛け算オペレータを使って書くことができる。

>>> a = [0] * 5 # すべての要素が0で、要素数5のリストを作成
>>> a
[0, 0, 0, 0, 0]

しかし、上記のような 0 という数値（immutable オブジェクト）ではなく、 mutable　オブジェクトを入れると大変なことが起こる。
こちらで詳しく解説されているので、詳細は省いて実際の挙動を見ていく。

# 要素 `0, 1, 2` を持つリスト、を5つ持つリストを作成
>>> b = [[0, 1, 2]] * 5
>>> b
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
# 0 番目のリストの 1 番目の要素（＝1）を 2 に変更する
>>> b[0]
[0, 1, 2]
>>> b[0][1] = 0
>>> b[0]
[0, 0, 2]
# しかし、すべてのリストで値が変更されてしまう。
>>> b
[[0, 0, 2], [0, 0, 2], [0, 0, 2], [0, 0, 2], [0, 0, 2]]

list は mutable オブジェクトなので、上記のような作り方をすると識別値（id）が同じオブジェクトでリストが満たされてしまう。
その結果、一つの要素だけを変更しているつもりでも、リスト内の全ての要素が変更されてしまう。
これは、同じく mutable オブジェクトの dict やユーザ定義クラスでも同じことが起きる。

# dict でも同じことが起きる
>>> c = [{"d": 1}] * 5
>>> c
[{'d': 1}, {'d': 1}, {'d': 1}, {'d': 1}, {'d': 1}]
>>> c[0]["d"] = 2
>>> c
[{'d': 2}, {'d': 2}, {'d': 2}, {'d': 2}, {'d': 2}]

# ユーザ定義クラスでも同じことが起きる
>>> class E():
...     def __init__(self):
...         self.name = "E"
... 
>>> e = [E()] * 5
>>> e    # すべて同じ id であることが確認できる
[<__main__.E object at 0x7f9be776abe0>, <__main__.E object at 0x7f9be776abe0>, <__main__.E object at 0x7f9be776abe0>, <__main__.E object at 0x7f9be776abe0>, <__main__.E object at 0x7f9be776abe0>]
>>> e[0].name = "F"
>>> [ee.name for ee in e]
['F', 'F', 'F', 'F', 'F']

対処法1. リスト内包表記で初期化

一番すんなりいく解決策。

>>> b = [[0, 1, 2] for i in range(5)]
>>> b
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> b[0][1] = 0
>>> b
[[0, 0, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

対処法2. リスト内包表記 + zipを使う

zip でなんとか無理やりやってみたが、これは逆に手間が増える印象。

>>> b = [list(z) for z in zip([0]*5, [1]*5, [2]*5)]
>>> b
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> b[0][1] = 0
>>> b
[[0, 0, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

対処法3. 掛け算オペレータ + 代入時に新オブジェクト生成

掛け算オペレータをどうしても残したいなら、代入時に新idのオブジェクトを差し込むという手も。
膨大にリストの要素があって、なおかつほとんどは同じ値でいい場合はメモリの削減になるかも？

>>> b = [[0, 1, 2]] * 5
>>> b
[[0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]
>>> b[0] = list(b[0])
>>> b[0][1] = 0
>>> b
[[0, 0, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2], [0, 1, 2]]

結論

素直にリスト内包表記で書くべし。