* Fully general. By this I mean capable of solving BQP problems in polynomial time. This excludes D-Wave machines, for example.
* Sufficiently large. 100 qubits would probably enable qualitative advances in cryptanalysis.
* Low enough error rate. This is a slightly redundant requirement, as too high an error rate would provably prevent the computer from being asymptotically faster than classical - which is what we care about.
The last requirement is due to the quantum threshold theorem[1]. Briefly, there is an error rate below which quantum computing is possible and above which it is not. The precise value is not known but it is probably over 1% and, at least for some kinds of circuits, under about 40%. That means that at the theoretical level, the task is to create a model of computation that has as high a threshold limit as possible, and then to design an error correcting scheme that comes close to that limit. This is something that a secret agency could plausibly do in-house.
However, there is then the question of implementing the model of computation in a physical system, with a sufficiently low error rate. NSA, GCHQ etc. are not known to have this sort of experimental expertise - they would probably have to contract it out (and indeed this is the major piece of new information in the article). The history on fundamental advances over civilian technology shows that this normally depends on co-opting basically the entire research community working in the field - as in radar, nuclear weapons, stealth etc. This is not at all the case for experimental quantum computing, which is not in practice treated as a 'sensitive' field.
Thus it is my opinion that the NSA may well already have some theoretical tricks up its sleeve that it can use in the future for a decent edge, but is unlikely to get the opportunity to use them before quantum computing becomes considerably more feasible in the unclassified world.
[1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem. Bounds lifted from http://arxiv.org/abs/0802.1464. Qualifications: I studied the mathematics of quantum computing as a Masters student, although I can't claim to still be current on the state of the art.