The answer is it depends, just like any other phoneme.
Changes in tonal system are fairly common, and examples of "speech varieties" that are still considered (more or less) the same by their own communities include:
- Southern Vietnamese has merged the hỏi and ngã tones (to my ears the merged tone has characteristics of both, but is closer to ngã), and Southern Vietnamese has a noticeably different contour for the nặng tone which sounds like the Northern hỏi tone (low falling-rising).
- The Fuqing dialect (a variety of Min Dong / Eastern Min, one of the Sinitic family) has undergone a change (through the 70s-00s?) where the "younger generation" (ill-defined, but more or less modern generation) have a new pattern of tone sandhi where for certain combinations both earlier and later lexemes change tone. The "older generation" have the more common pattern where only non-final syllables change.
- Zhongshan Cantonese (including the native one of Macau) merges the 2nd and 5th tones into one rising tone, although the 2nd tone (higher rising tone) reappears in certain lexically derived phonemes.
Compare this with phonemic mergers as the marry-merry-Mary merger in English or the nasal vowel shift in Metropolitan French vs Quebec French, or distinción/seseo/ceceo in Spanish. The perception of a whether something is a different language also requires a lot more than a shift in sounds, whether that sound change is a tonal system or consonants or vowels.
I'm not sure there's much data describing speech varieties with a tone system change but without a large scale change in other phonological features. I would posit that the nearest situation to that would be the local dialects of Mandarin:
- the four tone system of Beijing (and hence Standard Mandarin);
- the five tone system (where one is actually a glottal stop) is quite common in the Jianghuai region (Lower Yangtze, basically around Nanjing) and in conservative varieties of Southwestern Mandarin;
- three tone systems (usually with the historical 平 píng tones merged) exist in the far western reaches of Central Plains Mandarin e.g. in Gansu.
(Neutral tones also come into play, and they differ too, but there's a deep grammatical interaction there.) However, a lot of these have distinct differences in vowels and consonants too.
Even between Beijing and Tianjin, both ostensibly four-tone systems with relatively similar phonologies but different realisations of tones, but also very different tone sandhi systems, are perceived as different "speech varieties" with some but limited mutual intelligibility. Then again, lexis differs too; there's also very different phonological reduction processes.
Ultimately, the question as it stands is a little bit too theoretical to be answered in any meaningful way. But the evidence (at least in the East and SE Asian sprachbund) suggests that there's not much difference to any other phonemic system change.