I got access to a @me.com account a few hours ago, and here is my analysis.
Apple's iCloud IMAP servers support two authentication methods (advertised via IMAP's CAPABILITY command): SASL PLAIN and the default IMAP method.
My app, when seeing this, chooses the more sophisticated SASL PLAIN. Since the iCloud outage on Feb 28 (maybe before, too?), this method no longer accepts full email as the login name.
Changing the login in my app's account setup from "user@me.com" to just "user" is one workaround (thank you again, @johnsof).
The stock Android Email app does not support SASL PLAIN, only the default IMAP authentication method, which continues to work either way: with and without the @me.com / @mac.com part.
As for the discrepancy between Mac Mail and Apple's own help page, "isn't it ironic, don't you think"?
@NJRonbo, @yaps - thank you for confirming that the "remove domain name" workaround is working for you, too.
I'll be adding a kludge in the app's authentication code for this, and releasing an update, since not everyone who's ran into the issue will see this discussion.