Pub's job is to look at your dependencies and select the best versions for them. Given things like shared dependencies, that's surprisingly hard. NP-complete, in fact.
So our initial version solver for pub was a very simple one. It would always terminate in a reliable amount of time, but that meant it could fail to find a solution to your package's constraints even when a solution existed.
One area where that's painfully obvious is SDK constraints. Because the Dart SDK itself is changing rapidly, any package likely only works with one or a couple of versions of the SDK. A while back, we added support so you could note which versions of the SDK your package supports.
Unfortunately, pub's solver was too simple to do take advantage of that. Instead, it would just pick the latest versions and then yell at you when the versions it picked didn't work with your SDK. This was better than silently picking incompatible versions, but not by much.
We just finished landing a new version solver into bleeding_edge. This solver does do backtracking (backjumping actually) and it can and will select versions of packages that work with your SDK even if that requires transitively downgrading other packages along the dependency chain. Awesome!
However, this also means that now there's a potentially exponential chunk of code right in the middle of pub that has had no real-world usage yet. Scary! Pub has pretty solid tests, and I've run the new solver against every version of every package on pub.dartlang.org without a problem, but nothing compares to the real world.
So, with luck, this means everything will just get more awesome and stable.
But, there is a chance that your package could have a dependency graph that falls through the solver's heuristics and tickles some pathological behavior. If you see pub being very slow or failing in an unexpected way, please do file a bug. When you do, please run:
$ pub --verbosity solver install
and include the log output. I expect we will have to tune some things once we get a better picture of how real usage affects it.