Instalé el plugin PushPlugin en Phonegap 3.1 y si bien el envío de mensajes push fue exitoso, no se desplegaba nada en la barra de notificaciones (statusbar) de Android.
Estuve buscando en varias partes pero al final encontré una solución: en el archivo GCMIntentService.java, agregué la creación de la notificación (fuera de la comprobación), esto tiene el inconveniente que un mensaje push siempre lo mostrará en las notificaciones, aún si la aplicación está abierta. Es una solución un tanto sucia, pero funcional.
Actualización: después de hacer unas pruebas más, volví a dejar el plugin como estaba y sólo añadí en el archivo PushPlugin.java en la función "public void onDestroy()" el valor false a la variable gForeground, con eso ya funcionó como esperaba.