Have you actually tried using it on a phone with no Google Play Services? I'm involved with the project and I remember someone reporting it works just fine. Vector for Android falls back to polling if GCM isn't supported/working afaik.
If Matrix adds something like XEP-0357 Push Notifications, enables verifiable builds & FDroid distribution, plus gets full featured XMPP bridge implementations done, then I think you're onto a winner. It gets extremely hard to convince people to install N+1 different IM clients once N>5, let alone the >10 that're becoming common. The XMPP Push XEP is working fantastically in Conversations IM and extremely fast too BTW (much snappier than Signal at least).
Congratulations on your work on the Olm implementation too!!! Now that Signal Protocol has been locked up in legalese (turns out Open Whisper WEREN'T really open), you guys are THE leading E2E implementation. It's really a fantastic contribution to the community and we owe Matrix devs a huge thank you!
Glad you like Olm :) I think OWS are trying to find a way for their impl to be appstore compatible too, so hopefully the user wins twice over!
Re OWS; yes, I still keep some small hope that they've just been too preoccupied and not completely thought/worked things through. People are human and they've clearly had a lot going on! Their position as stated really did surprise a lot of people. Matrix.org's views on decentralisation certainly sounds FAR closer to the future I'd like to see for the net. Being able to evolve or change clients and integrate new technologies, without cutting off the entire network, seems clearly a very good thing indeed.
It's a double-ratchet, very similar to Signal protocol, but unencumbered by the GPL/iOS licensing issues that Signal's implementation has.