diff -ruN src/lib/spack/spack/spec.py src-new/lib/spack/spack/spec.py
--- src/lib/spack/spack/spec.py	2018-05-25 13:52:09.727589903 +0200
+++ src-new/lib/spack/spack/spec.py	2018-05-25 13:55:17.927589185 +0200
@@ -115,7 +115,6 @@
 from llnl.util.tty.color import cwrite, colorize, cescape, get_color_when
 
 import spack.architecture
-import spack.compiler
 import spack.compilers as compilers
 import spack.error
 import spack.parse
@@ -184,7 +183,7 @@
 
 #: This map determines the coloring of specs when using color output.
 #: We make the fields different colors to enhance readability.
-#: See llnl.util.tty.color for descriptions of the color codes.
+#: See spack.color for descriptions of the color codes.
 color_formats = {'%': compiler_color,
                  '@': version_color,
                  '=': architecture_color,
@@ -1833,13 +1832,26 @@
         changed = True
         force = False
 
+        user_spec_deps = self.flat_dependencies(copy=False)
+
         while changed:
-            changes = (self.normalize(force, tests),
+            changes = (self.normalize(force, tests=tests,
+                                      user_spec_deps=user_spec_deps),
                        self._expand_virtual_packages(),
                        self._concretize_helper())
             changed = any(changes)
             force = True
 
+        visited_user_specs = set()
+        for dep in self.traverse():
+            visited_user_specs.add(dep.name)
+            visited_user_specs.update(x.name for x in dep.package.provided)
+
+        extra = set(user_spec_deps.keys()).difference(visited_user_specs)
+        if extra:
+            raise InvalidDependencyError(
+                self.name + " does not depend on " + comma_or(extra))
+
         for s in self.traverse():
             # After concretizing, assign namespaces to anything left.
             # Note that this doesn't count as a "change".  The repository
@@ -2190,7 +2202,7 @@
 
         return any_change
 
-    def normalize(self, force=False, tests=False):
+    def normalize(self, force=False, tests=False, user_spec_deps=None):
         """When specs are parsed, any dependencies specified are hanging off
            the root, and ONLY the ones that were explicitly provided are there.
            Normalization turns a partial flat spec into a DAG, where:
@@ -2219,27 +2231,34 @@
 
         # Ensure first that all packages & compilers in the DAG exist.
         self.validate_or_raise()
-        # Get all the dependencies into one DependencyMap
-        spec_deps = self.flat_dependencies(copy=False)
+        # Clear the DAG and collect all dependencies in the DAG, which will be
+        # reapplied as constraints. All dependencies collected this way will
+        # have been created by a previous execution of 'normalize'.
+        # A dependency extracted here will only be reintegrated if it is
+        # discovered to apply according to _normalize_helper, so
+        # user-specified dependencies are recorded separately in case they
+        # refer to specs which take several normalization passes to
+        # materialize.
+        all_spec_deps = self.flat_dependencies(copy=False)
+
+        if user_spec_deps:
+            for name, spec in user_spec_deps.items():
+                if name not in all_spec_deps:
+                    all_spec_deps[name] = spec
+                else:
+                    all_spec_deps[name].constrain(spec)
 
         # Initialize index of virtual dependency providers if
         # concretize didn't pass us one already
         provider_index = ProviderIndex(
-            [s for s in spec_deps.values()], restrict=True)
+            [s for s in all_spec_deps.values()], restrict=True)
 
         # traverse the package DAG and fill out dependencies according
         # to package files & their 'when' specs
         visited = set()
 
         any_change = self._normalize_helper(
-            visited, spec_deps, provider_index, tests)
-
-        # If there are deps specified but not visited, they're not
-        # actually deps of this package.  Raise an error.
-        extra = set(spec_deps.keys()).difference(visited)
-        if extra:
-            raise InvalidDependencyError(
-                self.name + " does not depend on " + comma_or(extra))
+            visited, all_spec_deps, provider_index, tests)
 
         # Mark the spec as normal once done.
         self._normal = True
diff -ruN src/lib/spack/spack/test/conftest.py src-new/lib/spack/spack/test/conftest.py
--- src/lib/spack/spack/test/conftest.py	2018-05-25 13:52:09.731589903 +0200
+++ src-new/lib/spack/spack/test/conftest.py	2018-05-25 13:56:19.019588952 +0200
@@ -611,7 +611,11 @@
             if not conditions or dep.name not in conditions:
                 self.dependencies[dep.name] = {Spec(name): d}
             else:
-                self.dependencies[dep.name] = {Spec(conditions[dep.name]): d}
+                dep_conditions = conditions[dep.name]
+                dep_conditions = dict(
+                    (Spec(x), Dependency(self, Spec(y), type=dtype))
+                    for x, y in dep_conditions.items())
+                self.dependencies[dep.name] = dep_conditions
 
         if versions:
             self.versions = versions
diff -ruN src/lib/spack/spack/test/spec_dag.py src-new/lib/spack/spack/test/spec_dag.py
--- src/lib/spack/spack/test/spec_dag.py	2018-05-25 13:52:09.735589903 +0200
+++ src-new/lib/spack/spack/test/spec_dag.py	2018-05-25 13:57:30.355588680 +0200
@@ -26,6 +26,7 @@
 These tests check Spec DAG operations using dummy packages.
 """
 import pytest
+import spack
 import spack.architecture
 import spack.package
 
@@ -102,6 +103,44 @@
         assert ('z' not in spec)
 
 
+@pytest.mark.usefixtures('config')
+def test_conditional_dep_with_user_constraints():
+    """This sets up packages X->Y such that X depends on Y conditionally. It
+    then constructs a Spec with X but with no constraints on X, so that the
+    initial normalization pass cannot determine whether the constraints are
+    met to add the dependency; this checks whether a user-specified constraint
+    on Y is applied properly.
+    """
+    default = ('build', 'link')
+
+    y = MockPackage('y', [], [])
+    x_on_y_conditions = {
+        y.name: {
+            'x@2:': 'y'
+        }
+    }
+    x = MockPackage('x', [y], [default], conditions=x_on_y_conditions)
+
+    mock_repo = MockPackageMultiRepo([x, y])
+    with spack.repo.swap(mock_repo):
+        spec = Spec('x ^y@2')
+        spec.concretize()
+
+        assert ('y@2' in spec)
+
+    with spack.repo.swap(mock_repo):
+        spec = Spec('x@1')
+        spec.concretize()
+
+        assert ('y' not in spec)
+
+    with spack.repo.swap(mock_repo):
+        spec = Spec('x')
+        spec.concretize()
+
+        assert ('y@3' in spec)
+
+
 @pytest.mark.usefixtures('mutable_mock_packages')
 class TestSpecDag(object):
 
@@ -300,18 +339,19 @@
         with pytest.raises(spack.spec.UnsatisfiableArchitectureSpecError):
             spec.normalize()
 
+    @pytest.mark.usefixtures('config')
     def test_invalid_dep(self):
         spec = Spec('libelf ^mpich')
         with pytest.raises(spack.spec.InvalidDependencyError):
-            spec.normalize()
+            spec.concretize()
 
         spec = Spec('libelf ^libdwarf')
         with pytest.raises(spack.spec.InvalidDependencyError):
-            spec.normalize()
+            spec.concretize()
 
         spec = Spec('mpich ^dyninst ^libelf')
         with pytest.raises(spack.spec.InvalidDependencyError):
-            spec.normalize()
+            spec.concretize()
 
     def test_equal(self):
         # Different spec structures to test for equality