> Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.

I'm not real good at these sorts of details, but I'm struggling more than usual here. From what you say, and from things I think I know:

* Planar graph 3-colouring (P3COL) is NP-complete;

* Therefore 3-SAT can be reduced in polynomial time to P3COL;

* There is an algorithm for P3COL that runs in 2^O(sqrt(n)) time;

* Therefore there is an algorithm for 3-SAT that runs in 2^O(sqrt(n)).

That doesn't feel right ... where is the error?