Layman Interpretation: Quantum Factoring Algorithm
The problem stems from the fact that your understanding of quantum computing (as outlined in the question) is incorrect. Certainly quantum computers are poorly explained in most popularizations. A quantum computer cannot simply check if a solution exists within a superposition deterministically, let alone in unit time.

The most general representation of the quantum state of $n$ qubits is the $2^n \times 2^n$ density matrix $\rho$, where the diagonal entries correspond to the probability of finding the system in a particular classical state, and the off diagonal entries indicate the phase of the superposition (going to 0 for classical probability distributions). 

Any quantum algorithm can be seen as a unitary operation followed by some measurement in the computational basis. Given an initial input state $\rho$, it will evolve to $\rho&#39; = U\rho U^\dagger$. The most general set of measurements that can be performed are called positive operator valued measurements(POVMs), where each measurement outcome $i$ is associated with a positive sei-definite Hermitian operator $P_i$ and the probability of outcome $i$ is given by $p_i = \mbox{Tr}(P_i \rho)$ (and hence $\sum_i P_i = \mathbb{I}$).

Within these constraints the operations you describe simply are not possible.