First a quick note - normally when Chinese talk about "dialects", what they mean is "languages". For example, Shanghainese and Mandarin are two different Chinese languages, not two different dialects of Chinese. Not a big deal, but I thought our Chinese members might want to know how to correctly talk about them in English.
I don't find it encouraging when I get told how great my Chinese is after 你好, but this is common behavior of native speakers in all the languages I learn. As others have mentioned, tones are more important to Mandarin speakers than initials and finals. That's because there is a lot of acceptable regional variation of initials and finals, but little variation of tones. It's not "wrong" to pronounce "shi" as "si"; it's an accepted variation, common in parts of the South. It's not "standard Mandarin", but it's not wrong. However, pronouncing the 1st tone as a 4th tone, which many Chinese who don't grow up speaking Mandarin occasionally do incidentally, isn't acceptable in most cases.
That being said, I sometimes hear Taiwanese pronouncing words with different tones, usually using 1st instead of 4th, than northern mainland speakers. But this type of thing is much rarer than variations in initials and finals.
So if they think you sound like a 外國人, it's probably tones. But it might also be something that's rarely taught. There is often a stressed word in a sentence. "When the tone(s) in a stressed word is mispronounced, the sentence will frequently sound quite bad to native ears, but when the stressed word is pronounced correctly, the other tones will often fall in line." Here is an article about this:
http://www.sinosplice.com/life/archives/2008/12/10/toward-better-tones-in-natural-speech