Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which is false.
Correcting myself, the bound is worse than exponential (so read "at least exponential in N"), but the point I wanted to make is that it is explicit.
Again, this follows from the general theory of algebraic numbers: the degree and height of a sum, product or root of algebraic numbers can be bounded explicitly (resultants + Mignotte bound for factors), and finally root separation bounds can be applied to the resulting polynomial.
The author says that this problem is in PSPACE. That's not obvious to me because I don't know how you sum arbitrarily long binary numbers in polynomial space.
However if you and he are both right that would suffice to prove P != PSPACE, so this problem is potentially very important. Unfortunately I don't even know what this kind of problem is called, which makes googling a bit difficult.