For a few exceptions to the tone/syllable-structure correlation, look at the Chatino languages — members of the Zapotecan branch of the Otomanguean family. Several of them have complicated tone systems and a syllable structure that allows some seriously gnarly consonant clusters.
Here is a paper on San Juan Quiahije (SJQ) Chatino that goes into some detail on the consonant clusters. In this particular variety, the maximal syllable is NCCVN or NCCV7. In other words, you can have a nasal and up to two other consonants in a cluster at the start of a syllable, and a nasal or a glottal stop at the end of the syllable. So this allows syllables like nskwan or ngya7. Also, both consonants in the initial cluster can have various sorts of secondary articulation. (For example, jwjya7 is a single CCV7 syllable, with jw and jy corresponding to IPA /xʷ/ and /xʲ/.)
I'm afraid I can't find a good English paper on tones in SJQ Chatino that's available online. If you can read Spanish, try this one, which goes into a good bit of detail. Anyway, SJQ Chatino has ten distinct tones, and also some fairly complicated interactions between tones in adjacent syllables.
(Disclaimer: The author of the linked paper is a classmate of mine. I'm not an expert on Chatino, I just work down the hallway from a few people who are.)
Edit: Aaron says above that "in order for tone to arise in a non-tonal language, some other phonological contrast is reanalyzed as tone," and that this tends to lead to phonological simplification. This is probably true. But in the Chatino languages, tone didn't arise out of some other feature. As far as we can tell, they've always been tonal. The proto-language of the entire family is reconstructed with tone, and so there was no need for it to arise out of anything.
The current theory is that the Chatino languages are descended from a polysyllabic language with a complex tone system — but that some of them (like SJQ Chatino) lost all their unstressed vowels. Those ended up as monosyllabic languages; they still have the same complex tone system they always had, but they also have those big gnarly consonant clusters where the intervening vowels have disappeared.
This isn't meant as a criticism of Aaron's answer. I just wanted to elaborate a bit on the historical difference between Chatino and (for example) Mandarin, since I think it sort of clarifies the typological picture.