I've just been struggling for a few days to get access to my Telegram account on my de-Googled phone.
It seems to be a common problem, but in my case I was overlooking one important point.
Now its fixed I need to write this note for future reference.
