We've been using Parse for about a month in building the backend for an iOS app and we are loving it. It is very simple to use and still pretty powerful. Also, Parse is pretty good at responding to questions quickly.
They have everything we need in regards to notifications. They allow us to send notifications to everyone at once, or allow users to be able to push notifications sent when they receive a message from another user.