I have a few hundred users with different tenents set up with 365 business basic accounts. I never had any issue adding their email account using the native android mail app - selecting exchange activesync. I had a client call and when she tried to add her account on a new phone (worked fine on her previous android phone) it circles around for a bit and finally pops up with the manual settings (which won't work).
I tested on my phone which has my 365 business basic email account working on it without issue. I had the exact same issue. OWA works fine for her account. Is MS rolling something out to force users to upgrade their account subscriptions or is this something that can be fixed?