Me too. This is the sort of thing that would traditionally be hidden as n lg n ^ (1 - eps) for some eps > 0, but it's much more amusing this way.

No way this is the correct upper bound, and I imagine it'll get refined fairly quickly. IIRC, the GapCVP results were released with a 1/n^400 complexity term, but people quickly got it down to 1/n^8 by more careful accounting.