I'm a native Russian speaker, and I decided to learn Mandarin, because it's linguistically almost the opposite of Russian.
I had no problems with tone pronunciation, but tone recognition was indeed much trickier. I still often get lost when listening to fast speech although I can follow formal speech (news) usually without problems.