There is nothing unique, special or weird going on here, there is only the usual slog of figuring out what an individual mail client requires and offers, and what the mail server provides and can offer, and aligning the two within your local expectations and needs.
OS X Server uses standard Unix mail server tools. Postfix and Dovecot. And again, there is nothing special, weird, or unique here.
Check your mail server logs for details around the connection failure. Assuming you see the connection error arriving, of course, and that's a clue in itself. You'll want and need to look at both the IMAP or POP logs, and the SMTP logs.
The usual triggers are the firewall settings, the particular required ports for your mail server configuration, whether SSL is used or not, and possibly the encoding of the credentials.
Check with the Android client settings, with the Android documentation, and possibly then with an Android forum around what your particular client requires, when connecting with Postfix and Dovecot tools. (These are standard Unix tools, so I'd expect there are Android-specific discussions around the network. Here's one discussion, though the trigger for what that Android user encountered is probably a firewall block against outbound TCP port 25 connections from random boxes — boxes that are not known mail servers — that is increasingly implemented around the 'net.)
And FWIW, OS X Server 10.6 has a layer of management tools atop Postfix with Server Admin key among these, and I'd manage via those first and not via the direct postfix commands. But the lower-level postfix commands do work on OS X Server, if you're looking around. In other words, read-only, don't use the lower-level Postfix tools to make changes, unless Server Admin et al don't allow you access to the setting.