Same, I'm basically tone deaf and just assumed that Mandarin wouldn't be accessible to me. But then I finally decided to give it a go, and turned out to not be much of an issue at all. I also find that it's easier to remember the tones in a context of a sentence. It's a lot like when you put an accent on different words when you speak English, so you can just memorize the cadence of the sentence, and you'll start learning the tones implicitly.