We don’t teach tones. (By “we”, I mean myself and the people who’ve trained with me. There are still TPRS people who insist on teaching or drilling tones, not realizing that it’s no different from drilling spelling. It’s still rules-and-output.) And don’t even get me started on “traditional” teaching, where the student sits in the language lab for three or four days (I am not making this up!) mindlessly repeating syllables. I can still hear the voice of a certain well-loved teacher at a Taiwan language center echoing over the three floors the language center covered, spitting out syllable after syllable. I assume someone was repeating after him, or else he’d just been doing it so long it had become some sort of meditation mantra for him.
If you start beginners using tonal spelling, color coding, and getting lots and lots and LOTS of good, distinct, clear, slow input, they will develop tones. On their own. We have recordings of students in the first two weeks of class who, well, have tones. Which people seem to think is unusual. I’m just used to it, I guess. We teach a minimal pair (two words that differ by only one sound) on the first day: Kù vs. KŪ. We don’t belabor the point — we just attach a directional gesture to each word, and make sure the difference in meaning is clear. That’s the most effective way to make the point that tones matter, without freaking everybody out. And, as I said, it works.
But for the “slosher” — the slightly more advanced student of Chinese who really hasn’t gotten anywhere yet, is feeling frustrated about his learning, and who has probably invested a lot of time and effort into memorization, tone issues are usually a major concern. But there isn’t just one kind of “tone problem”. You need to ask the student:
Which kind of tone issues are you having?
1. You aren’t sure which tone something is in the first place (memorization issue [for those taking most classes], or [better] you get new words through repeated oral input, but you haven’t yet gotten enough input/heard it enough times).
2. You know what tone it’s supposed to be, but you accidentally said the wrong tone while speaking.
3. You know what tone it’s supposed to be, but six times out of ten, if you try to pronounce a certain tone, people can’t tell which one you’re trying to pronounce.
4. It actually has nothing at all to do with your tones; your basic syntax is so messed up that no one can make out what you’re saying. Most students who say they are having “tone problems” actually are having syntax and usage problems (or having them in addition to tone problems. The test for this one is: can people understand you in “normal speech”, but your communication breaks down if you need to communicate names or addresses out of context?
The solutions for these problems (singly or in combination) will be different, and the amount of time/effort it takes to overcome them will also be different. There’s not much to be done for #2 as a quick fix, because if you slow down and concentrate on tones, you’re sacrificing fluency, which may have a worse impact on communication and also on how you’re perceived as a person. For #1, adopt some sort of tonal spelling — I use TOP, but then again, I made it up in response to this kind of problem in my own Mandarin some years back. For #3 it’s drills with someone who understands how to explain the tones — and I don’t mean the “tones are like this” page in most textbooks, which is usually wrong on at least a couple of things. For #4, it depends on how long one has been studying Mandarin and how patient one is, because “fixing” crooked Chinese calls for massive input (ideal) or drilling (not ideal but more in line with what most teachers are equipped to offer) and going back over things that you think you already learned.
Unless a student is getting Chinese through massive highly-comprehensible input, usually it’s better to concentrate on making the syntax and usage as accurate as possible. The tones will (or won’t) follow, but toneless Chinese is perfectly comprehensible in the majority of situations if the grammar and word choice are correct. That’s generally a big “if” with students taught using rules-and-output (and most “communicative” Chinese programs are actually based on this, if you scratch the surface). Tone drills are the easiest and most visible solution, but in my experience, not close to being really effective.