А системная настройка "фоновые данные" (пока не смотрел где это теперь.. было в разделе Использование данных) включена?
Как насчет "фоновая синхронизация"?
Да, насчет икноки в статусной строке -- по умолчанию отключена на 5.0 и выше, т.к. отображается на экране блокировки. Попробуйте включить, настройки программы -- интерфейс, ну просто для наглядности.
Диагностика -- отладочные логи это наши лучшие друзья.
См. ссылку ниже в моей подписи, а там "отладка неправильной работы".
Просто включите пуш почту, и оставьте программу минут на 10.
Затем проверьте почту "вручную" разок (в одной учетке, не всех, так проще отслеживать в логе).
И вот здесь уже можно присылать лог.