Newly paired controller on Android stops after first use

The title says it all... Do you know a workaround to make them functioning properly again?

After the first disconnect from bluetooth or reboot when the controllers got paired, they stop working for that phone/tablet.

I saw one post about that issue but can't find it any more. :(