Thanks for the advice. Interestingly, after disabling security it connects immediately. But if I enable any type of security (WEP or WPA), it fails to connect. I suppose I could run with it open but I'm not very comfortable with that since I plan to start using an astronomy site that will have a lot of other people nearby who are also going to be using telescopes and astrophotography rigs - it wouldn't be very good if someone connected (either accidentally or on purpose) and messed with my RPI.
So the problem is definitely related to Wi-Fi security and Android, I just don't know how to sort that out.