Trouble with Google's ImmutableSet

Are you using the older Google Collections and not Guava? I'd be curious to see your results with the latest Guava release 14.0.1 which includes a change to use MurmurHash3's mixK1 for hash bit smearing:

https://code.google.com/p/guava-libraries/source/detail?r=69...