For lack of commenting rights, but merely intended as a comment to user568458's most excellent answer:
What he describes (first, you saying something in MSA, then receiving an answer in the local dialect) can sure happen a lot. To me, it happened much more often that first I got a blank stare, then a loud laugh, then the next thing I know, the person I was trying to talk to calls their friends while I'm still wondering whether I was being laughed at. Then the next think you know you're being paraded around as the guy from Germany (Soccer! Mercedes! BMW!) who speaks "better Arabic than you guys do".
If I was allowed one wish, it would be to travel back in time to the first day of my Bachelor's in Arabic Studies and to have the strength to ditch all those Professors' advice and start with a dialect (preferably Syrian Arabic and more precisely the one spoken in and around Damascus). Syrian Arabic specifically because of all the native speakers of it that are now in Europe but also because there's an excellent textbook for it now (at least in German - please do tell if you know of a good English one).
Teaching any but the most skilled, talented, and driven students of Arabic the high language first can only serve to hamper their progress permanently and profoundly. Personally, I've gotten better at some of the dialects since, but as soon as the situation gets challenging socially or emotionally, I will forever fall back into MSA patterns - often preventing the communication as such from succeeding. Either because people start drifting off-topic, instead making the language itself the new topic again (which takes a lot of energy to reverse and keep it so) or, much worse, because people start feeling talked-down to.
On top of all that, unless you learn to understand at least some of the (often undocumented) grammar, vocabulary, melody and syntax of your conversation partner's dialect, you'll be forced to keep guessing your way through what they're trying to tell you based on the words you do understand. This effect can be more or less pronounced.
For example:
- At university (or wherever) you've learned to ask or be asked "أَيْنَ أَنْتَِ تَذْهَبِْ\ينَ؟" ("Where are you headed", ayna anta/anti tadhhab/eena, a phrase that once had me be the target of being made fun at for days by a General of one of the Gulf countries' domestic intelligence services, but that's a story for another day and place).
- Now, a speaker of Syrian Arabic would say "وين تروح\ي؟" (weyn troo7/i) Depending on your aptitude to transfer existing knowledge to new patterns, because of your knowledge of the vocabulary رَاحَ\يَرُوحُ and أَيْنَ, as well as the possible phonetic behaviours of weak radicals, even without asking anyone, you might figure it out sooner rather than later.
- Then you go to Morocco and a police officer at a border control station wants to know "فين غادي؟" (feen ghadi) and you might feel pretty panicky all of a sudden.
(At this point, though, also a remark on MastaBaba's answer: the "out-of-the-way" villages in, specifically, Oman (but not the south that he mentions, rather, the north) have, for a number of reasons, to me always been the places where I had the least trouble making use of that posh-sounding MSA, with people not only understanding without any strong feelings caused by the language itself, but also being able to respond in kind and without resorting to such high-level vocabulary that you in turn feel like you're out of your depth now.)
Of course everybody's different and also how much people are emotionally influenced by the communication situation they find themselves in differs a lot. In the experience of myself and some of my study colleagues, though, Arabic has a tendency to be heavier [than other non-indo-european languages] on the [natively indo-european] learner in terms of formation of new speaking (and thus, thinking) patterns and consequently, in terms of emotional workload while acquiring the language. To that extent I also disagree with user568458 in that having learned "one" (i.e. MSA) is a strong headstart in learning "the others" (i.e. one of the dialects).
In short: Yes! With the exception of the bare basics, go, learn a dialect (first)!