Pues nunca he trabajado con ello pero has probado a poner el banner en una app vacia y con version 4.0 compilado en un movil? Porque muchas veces el fallo puede venir de algun otro sitio que no nos lo marque adecuadamente el Logcat. En mi clase pasa mucho el no poner los permisos de la app y claro luego no funciona.
Tambien
veo que dicen que la primera vez puede tardas hasta 2 minutos y debes poner "testDevices" en el xml para decir que estas haciendo pruebas y que google no se enfade, puede ser el problema alguno de esos?que se te hayan olvidado los permisos, no probarlo en un movil o no darle tiempo la primera vez a que carguen?
De todas formas se que algunos de aqui tienen apps ya en google play con anuncios osea seguramente te podran ayudar pero necesitaran algun codigo o alguna cosa para mirar donde esta el fallo.