It is also pointless to shuffle a list object repeating the same item, but that is no reason to add a special case. Is there a real problem with allowing dictionaries and OrderedDict? It seems to behave sensibly if you give each item a unique value:

>>> D = {i: i * 100 for i in range(5)}
>>> D
{0: 0, 1: 100, 2: 200, 3: 300, 4: 400}
>>> shuffle(D)
>>> D
{0: 300, 1: 100, 2: 200, 3: 0, 4: 400}