Well, sort of.
It’s not a problem like you’d imagine. There’s essentially two types of tonal systems - register tones and contour tones. Languages with register tones simply use different pitches to distinguish certain syllables - a syllable can be high, or low, or (in some languages) in the middle. There’s a lot of languages with register tones in subsaharan Africa. To my knowledge, there’s no language with more than three register tones; the tonal systems in these languages are simple enough that they don’t tax the ability to handle pitches. Keep in mind that tone-deafness is not absolute, as mentioned above. While some people are less able than others to identify musical intervals, and things like that, it’s not as though they can’t distinguish a high sound from a low sound. Since register systems tend not to involve many different pitches, and since the distinctions are probably based more upon comparisons between neighboring syllables rather than an absolute idea of what the proper pitch should be, you can hear the difference no matter what. Especially since it’s only part of the phonological system of such a language - there’s lots of separate contextual data that’s assembled into figuring out what word someone said, and tone is only a part of it.
Contour systems are what yabob describes. An example are the Chinese languages. For instance, Mandarin has a high level tone, a falling tone, a rising tone, and a falling-rising tone. Each tone is distinguished by the shape of the pitch - how it falls and rises. Mandarin’s tone system is fairly simple, and each tone can be distinguished strictly based upon shape, without reference to absolute pitch at all. Some of the other Chinese languages are more complicated; Cantonese has six or seven (depending on dialect) and some of them share the same shape. Even so, the differences just don’t require making terribly subtle distinctions.
There’s some interesting research, though, that indicates that speakers of contour tonal languages tend to be fairly precise with the pitches they use to speak different tones - it’s an ability you develop as soon as you start talking, which trains the ear and voice to improve the ability to detect and create tones. In fact, one study suggests that absolute pitch (“perfect pitch”) is much more common among native speakers of tonal languages, to the point that it’s not at all rare. People receive intense training in it by virtue of speaking the language, which tends to eliminate the problem. Even for folks with no musical ear, though, being able to speak a tonal language doesn’t demand nearly the same ability to distinguish pitches that playing a musical instrument does.