When did support for dictionary comprehensions make it into 2.x? I could've sworn it didn't used to work, but I just tried it in the shell and sure enough, it does in 2.7.3.
The order of items in the dictionary isn't stable, but the order of .keys() is guaranteed to be the same as the order of .values() (as long as you don't modify the dict in between calling one then the other).