Since no one seems to be posting a solution, I'll post the one I have. It is a classical problem that every integer has a multiple of the form $111\cdots\>100\cdot\>0$ (this can be proved using the pigeonhole principle). Removing the zeroes, and multiplying the rest by 19, we obtain a number of the form $2111\cdots\>109$ or 209. Removing the 0, and multiplying by 9 gives 261 or a number of the form $190\cdot\>071$. Removing the zeroes, we see that we only have to treat the two cases 261 and 1971. An easy (but tedious!) calculation proves the result.

well, i had a partial solution in the case $(3,n)=1$,which i did intend to post sometime but.... basically the ideas involved were rather interesting.note firstly that the number $n$ we start with can be made relatively prime to 10 by dividing out all the powers of 2 and 5(that is possible since it is equivalent to multiplying the number by 5 or 2 as the case may be and then dividing by 10(throwing away the last zero). now if the number is a prime $p$ that satisfies $\large(\frac{10}{p}\large)=-1$ i.e. 10 is no a square modulo $p$ then $10^{(p-1)/2}\equiv -1(\mod p)$ so that the algorithm would reduce $p$ to $11$. for 11 the following chain does the job; $11\rightarrow 506\rightarrow 56\rightarrow 28\rightarrow 14\rightarrow 7$. now the general idea is this: if we can get a multiple of $n$ which "includes" a prime of that sort(i.e. you can get such a prime after throwing away a few zeroes ) then you are through. now a prime whose last three digits are $011$ will certainly do the job(since then such a prime will be $3(\mod 8),1(\mod 5)$ and so $\large(\frac{2}{p}\large)=-1,\large(\frac{5}{p}\large)=1$. to do this suppose there exists a $t$ such that the sum of digits of $t$ is divisible by $n$,its last three digits are 011 and $(t,n)=1$. then consider numbers of the form $10^tnk+t$; for some large enough $k$ such a number will be prime(Dirichlet's theorem). in this case we are through again. to see this, note that since $(n,10)=1$ there exists some $k$ such that $10^k\equiv 1(\mod n)$.since the sum of digits of $t$ is divisible by $n$, we can get a multiple of $n$ to be $\tilde{t}$ which is $t$ along with some extra zeroes(this is because of the above observation-$10^k\equiv 1(\mod n)$). then $10^{\tilde{t}}nk+\tilde{t}$ is a multiple of $n$ and the algorithm reduces it to $10^tnk+t$ which is a prime of the required sort(choosing $k$ sufficiently large). thus finally all we need is a $t$ of the aforementioned type.this is easy since as $n>10$(else there is nothing to prove) there exists a multiple of $n$ of the form $a=11\cdots1$ and so there is also a multiple of $n$ which has only ones and with the number of ones also being a multiple of $n$(for instance $a\cdot (100\cdots01)$ with an appropriate number of zeroes).now consider $t=111\cdots 2011$.this will keep the sum of digits a multiple of $n$ and if $k|t,a$ then $k|t-a=900$ but by assumption that is not possible unless $k=1$ and that proves the last part.