Não, não há problema algum com a mudança de nome. Você ainda é um cidadão australiano e, se tiver alguma evidência para documentar a mudança de nome, isso será útil. Mas você não precisa de visto algum.
Eu sou um nacional duplo atualmente morando no Reino Unido e possuo passaportes do Reino Unido e da Austrália. Estou planejando um feriado para a Austrália em breve. No entanto, meu passaporte australiano está em meu nome de solteira (passaporte do Reino Unido no nome de casada).
Terei problemas para entrar na Austrália? Posso solicitar um visto eletrônico no meu passaporte do Reino Unido e apenas usá-lo, ou devo também levar meu passaporte australiano, mesmo que ainda esteja em meu nome de solteira?
Não, não há problema algum com a mudança de nome. Você ainda é um cidadão australiano e, se tiver alguma evidência para documentar a mudança de nome, isso será útil. Mas você não precisa de visto algum.
alguns países exigem, por lei, a entrada no passaporte específico do país, se existir, independentemente de outros passaportes que possuam.
Este gov australiano. página nacional dupla declara:
Entering and leaving Australia
All Australians, including dual nationals, should leave and enter Australia on their Australian passport. If you have a passport from another country you can use that for travel once you have left Australia. People trying to enter Australia as an Australian citizen but without an Australian passport will face difficulties and delays.
e
An Australian passport is the preferred and most conclusive proof of Australian citizenship when travelling. Dual nationals should use an Australian passport to enter and depart Australia.
Quanto ao seu nome - traga uma prova de mudança de nome, mas se você se registrou como casado no consulado australiano (como você deve ter em caso de mudança de estado civil) então isso não deve ser um problema, e mais ainda - você pode, se desejar, solicitar um novo passaporte gratuito devido à mudança de nome, conforme explicado em esta página dedicada a mudança de nome relacionada ao passaporte
Se você ...
marry or enter a registered relationship overseas and wish to assume your partner’s family name or add it to your own
você deve apresentar
an Australian RBDM name change certificate, because your marriage or entry into a relationship overseas cannot be registered by an Australian RBDM
(Eu realmente admiro o quão ordenado e fácil de encontrar toda essa informação é com um simples 2 seg. de pesquisa - Kudos para as autoridades relacionadas com a Austrália ..)
E assim como @ jcaron comentou em outra resposta - seu problema poderia ser mais com a companhia aérea do que com o oficial de imigração na Austrália e, de fato, o mesmo acima página de cidadãos nacionais declara ..
International airlines have an obligation to carry only appropriately documented passengers to Australia. Appropriate documentation for Australian nationals is an Australian passport. Appropriate documentation for a foreign national is a visa to enter Australia. If an Australian national attempts to board a flight to Australia without an Australian passport, airlines will likely be unable to verify their claim to Australian citizenship at the time of check-in and may refuse boarding
A esse respeito, devo dizer que eu também possuo vários passaportes com nomes diferentes (caso semelhante ao seu) e sempre que surgir uma dúvida com qualquer oficial em particular (seja companhia aérea ou imigração) eu apenas mostro o outro passaporte ou um formulário do consulado que indica a mudança legal do nome.