I verified my password multiple times on my linux desktop... with thunderbird extension and web browser login...
I simply can not login on my android device.. 4.1.2
Please tell me - are you referring to our Android app and if so - what version are you using?
Please try to go to the Todoist Settings -> Account on the web-app and change your password to something short without any special characters and see if you can then log in through the Android app.
Then, try to log out and change your password back and see if you can log in now.