Even though I still didn't manage to reproduce the behavior in a minimal example, here is what we observed:

$ spack load --dependencies py-cython py-pytest py-setuptools cmake py-multiarray py-numpy py-matplotlib "^python +ucs4"
$ module list 2>&1 | grep mock
 17) py-mock-2.0.0-gcc-4.9.2-itikmwv
 76) py-mock-2.0.0-gcc-4.9.2-5lzv2ds

and

$ spack find -fdv /5lzv2ds > out5lzv
$ spack find -fdv /itikmwv > outitik
$ diff out5lzv outitik 
3c3
<         ^py-pbr@1.10.0%gcc cflags="-O2 -march=core2 -pipe" cxxflags="-O2 -march=core2 -pipe" fflags="-O2 -march=core2 -pipe" 
---
>         ^py-pbr@1.8.1%gcc cflags="-O2 -march=core2 -pipe" cxxflags="-O2 -march=core2 -pipe" fflags="-O2 -march=core2 -pipe"

My guess is that this problem occured, because py-pbr got a new version between the install of two of the loaded packages, so that one of those now depends on @1.8.1 and the other on @1.10.0.

There are now two questions:

1. Is this intended behavior? I.e. should a package with depends_on("py-pbr@1.8:") resolve to py-pbr@1.8.1 or to @1.10.0 if py-pbr@1.8.1 is already installed and @1.8.1 and @1.10.0 are known to spack?
2. Should spack load perform a sanity check, i.e. check that the modules that are loaded only contain exactly one module per package?

In our case this wasn't a problem, and manually unloading py-pbr@1.8.1 made the environment consistent. However, that may not always be possible (think about depends_on("A@:1.10") and depends_on("A@0.9:")). I'll mark #3827 as WIP until question 2) is answered.