According to the researchers who cracked it, RSA-768 took an equivalent 2000 years to factor on a 2.2GHz single-core computer.
Using the complexity equation for the General Number Field Sieve with n=2^768 yielded 8.7*10^31 operations (calculated using Maxima). Let's naively assume a computer can perform 1 billion operations per second. Then that comes out to 2.73*10^13 years. That's off the reported value of 2.0*10^3 years by 10 orders of magnitude!
What am I missing? Calculations I did for other primes yielded similar over-estimates. Am I doing something wrong? Or is the complexity bound really just that loose?
There is an error in your "complexity equation". Replace the constant $\sqrt{\frac{64}{9}}$ by $\sqrt[3]{\frac{64}{9}}$. Wolfram Mathematica says, that if $N=2^{768}$, that $$\exp{\left(\sqrt[3]{\frac{64}{9}}(\ln N)^{1/3}(\ln \ln N)^{2/3}\right)}/10^{12}/3600/24/365=3.41\cdot 10^3$$
In view of Coppersmith's paper this constant can be $\frac{1}{3}(92+26\sqrt{13})^{1/3}=1.902$, with respect to some modifications of the method, and, so, result time is $1.9\cdot 10^3$.