Algunos países requieren por ley entrar con el pasaporte específico de su país si existe, independientemente de otros pasaportes en su posesión.
Esta página del gobierno australiano para nacionales con doble nacionalidad dice :
Entrando y saliendo de Australia
Todos los australianos, incluidos los de doble nacionalidad, deben salir e ingresar a Australia con su pasaporte australiano. Si tiene un pasaporte de otro país, puede usarlo para viajar una vez que haya salido de Australia. Las personas que intentan ingresar a Australia como ciudadanos australianos pero sin un pasaporte australiano enfrentarán dificultades y demoras.
y
Un pasaporte australiano es la mejor y más concluyente prueba de la ciudadanía australiana al viajar. Los de doble nacionalidad deben usar un pasaporte australiano para entrar y salir de Australia.
En cuanto al nombre - traiga una prueba de cambio de nombre, pero si se ha registrado como casado en el consulado australiano (como debería hacer en caso de cambio de estado civil), entonces esto no debería ser un problema, y además, puede, si lo desea, solicitar un nuevo pasaporte gratuito debido al cambio de nombre como se explica en esta página dedicada al cambio de nombre relacionado con el pasaporte.
Si usted...
se casa o entra en una relación registrada en el extranjero y desea asumir el apellido de su pareja o agregarlo al suyo
debería presentar
un certificado de cambio de nombre de RBDM australiano, ya que su matrimonio o entrada en una relación en el extranjero no puede ser registrado por un RBDM australiano
(En realidad admiro lo ordenada y fácil de encontrar que está toda esa información con una simple búsqueda de 2 segundos - Felicitaciones a las autoridades australianas relacionadas...)
Y al igual que @jcaron comentó en otra respuesta - su problema podría ser más con la aerolínea que con el oficial de inmigración en Australia y de hecho la misma página de nacionales con doble nacionalidad menciona...
Las aerolíneas internacionales tienen la obligación de transportar solo pasajeros debidamente documentados a Australia. La documentación adecuada para los nacionales australianos es un pasaporte australiano. La documentación adecuada para un extranjero es una visa para ingresar a Australia. Si un nacional australiano intenta abordar un vuelo a Australia sin un pasaporte australiano, es probable que las aerolíneas no puedan verificar su reclamo de ciudadanía australiana en el momento del check-in y pueden negar el embarque.
En ese sentido debo decir que también poseo varios pasaportes con nombres diferentes (caso similar al suyo) y cada vez que surge una duda con algún oficial en particular (ya sea de aerolínea o inmigración) simplemente muestro el otro pasaporte o un formulario del consulado que indique el cambio legal de nombre.
