> ... this is a crappy solution that's underusing Python. Please
> enlighten me of a better way!
>
> - Fencer
One thing that springs to mind is using the dict method .setdefault
<untested>
for dkey, vallist in old_dict.iteritems():
for val in vallist:
new_dict.setdefault(val, set()).add(dkey)
</untested>