Adding evaluationDependsOn(':b') (or dependsOn(':b')) at the beginning of the a/build.gradle file seems to achieve the intended result.

As described in 36.6.2. Configuration time dependencies [1], "On the same nesting level the configuration order depends on the alphanumeric position.". What I guess is happening here is that populating the configurations.runtime property is happening at configuration time, so that your fatJar task actually depends on the order in which the projects are evaluated.
This would explain why an evaluationDependsOn is enough to produce the correct result (note that it does not change the execution order!).

Of course, one might ask whether a compile project(':other') dependency should/could not automatically produce such a configuration dependency, but I'm guessing there are use cases where this would cause problems (examples, anyone?).

As a side note, most of the examples [2, 3] of producing a "jar-with-dependencies" using Gradle also use the archivePaths of other archive tasks. E.g.

 
project.tasks.withType(Jar).each {archiveTask ->
  copy {
    from archiveTask.archivePath
    into explodedDist
  }
}

from 'src/dist'
    into('libs') {
        from spiJar.archivePath
        from configurations.runtime
    }
}

[1] http://www.gradle.org/0.9-rc-1/docs/userguide/multi_project_builds.html#sub:configuration_time_dependencies
[2] http://www.gradle.org/0.9-rc-1/docs/userguide/multi_project_builds.html#sub:real_life_examples
[3] http://www.gradle.org/tutorial_java_projects.html#N1056B

Everything in the configuration closure of a task gets executed all the time you do something with the build (e.g. doing a clean). That means the compile configuration is always resolved. This can be an expensive operation even if everything is in the cache. Specially if done multiple times in a large multi-project build.

In the case above we have the additional problem that project(':b').configurations.compile is resolved before the build.gradle of project b is evaluated (therefore no commons-io in a-fatJar).

Solution: You can pass a closure to a from clause. That way the configurations when building the fat jar are resolved during execution of the jar task. Everything is properly configured by then.

 
task fatJar(type: Jar, dependsOn: jar) { 
  archiveName = "a-${project.version}-fat.jar" 
  depClasses = { configurations.runtime.collect { it.isDirectory() ? it : zipTree(it) } } 
  from(depClasses) { 
    exclude 'META-INF/MANIFEST.MF' 
    exclude "META-INF/maven/**" 
  } 
  from(sourceSets.main.classes) 
} 

BTW: You don't need to exclude the MANIFEST.MF anymore with Gradle trunk, this happens now automatically.

@Hans: if I understand your solution correctly you're simply delaying the evaluation of configurations.runtime by turning it into a "lazy" variable. If I read Jeroen's issue correctly, though, the following question remains: why is it possible to see a "half-constructed" (from the point of view of the project you're in) configurations.runtime in the first place?
In the context of this example: since project a depends on project b, should references to configurations.* in project a not always see all the dependencies that come from b? In other words, should there be a kind-of "safe publication" guarantee for configurations that come from dependent projects?

I would agree with you that the observed behaviour in this case is consistent with the documentation (so it's not a bug, in that sense). I think it's also valid to ask, though, whether this is logical behaviour from the developer's perspective.

Your question is absolutely valid. In fact what you are proposing is what we are heading for (trying to stay backwards compatible as much as possible).
Have a look at: http://docs.codehaus.org/display/GRADLE/Gradle+1.0+Build+Configuration+DSL