The thing to remember is that the single-particle mode, which the system is being condensed into, will not be 100% occupied in an interacting system. Interactions will mix single particle excited states and thus the number of particles in the single particle ground state will not be conserved. (i.e $[a^{\dagger}_0 a_0,H] \neq 0 $). But in the original system, particle number is still conserved.
The approximation that leads to the contradiction, is to ignore the occupation of the other single particle states when studying the excitation spectrum. Thus, when studying the excitation spectrum, you make an approximation that creates a system where the total particle number is not conserved. This is a valid approximation because, the occupation of the single-particle excited states is small and won't effect the excitation spectrum.
Roughly, the true ground state is:
$
\sum_n (a^{\dagger}_0)^{N-n}\sum_{\{i\}}\psi_i \prod_i ^n a^{\dagger}_i \left|\right>
$
where
$
\sum_{\{i\}}\psi_i \prod_i ^n a^{\dagger}_i \left|\right>
$
is some general n particle wave function involving the single particle excited states.
When you trace out the single particle excited states, you get a state that roughly looks like:
$
\sum_n (a^{\dagger}_0)^{N-n}\psi_n \left|\right>
$
For a weakly interacting system, $\psi_n$ will have the form of a coherent state. In reality, this won't be a pure state, but for a condensed system, it will closely approximate it (single particle density matrix will have a single dominate eigenvalue).
Now if you make an approximation that ignores the other n-particle wave functions, you are essentially treating this (particle non-conserving) coherent state as the ground state of your system(thus making the approximation that the system doens't conserve particles). It is valid to do this when studying the excitation spectrum since your excitations are pertubativly effected by small occupation of the other n-particle wave functions.
If you want use the same treatment for a strongly interacting system, you have to use renormalized parameters to account for the effects of the, now, non-negligible, single particle excited states. This works, because the spectrum of the weakly and strongly interacting systems are pertubativly connected.
