I think the answer is "no"; here is a sketch of an argument though I will have to go back and check the details. First, there is nothing special about invertibility here; if every invertible operator is approximable by operators with countable spectrum, then every operator is, just by translation. I claim the unilateral shift $S$ should not be approximable, because it is a Fredholm operator of nonzero index. The set of Fredholm operators is open, and the index is a continuous function on this set, so any sufficiently good approximant would have to be Fredholm of index -1. But I think that if a Fredholm operator has countable spectrum, then the index must be 0 (reason: if 0 is not isolated in the spectrum, then the range won't be closed, and if 0 is isolated (or the operator is invertible) then the index is clearly 0).
EDIT: Here is a proof that a Fredholm operator $T$ with countable spectrum must have index 0. We may clearly suppose $T$ is not invertible, so 0 is in the spectrum. The first claim is that 0 must be isolated--if not, then since the spectrum is a countable, compact set, 0 must be the limit of a sequence of isolated points in the spectrum. But each isolated point must be an eigenvalue, which means that $T$ would then have a sequence of eigenvalues tending to 0, and would not have closed range and not be Fredholm. So, 0 is isolated. But then $T+\epsilon I$ is invertible for all small $\epsilon$, and by the continuity of the index we have that $ind(T)=0$.