Australia has a new Prime Minister, the very competent Julia Gillard.  She is the first Australian PM since 1923 not to have been born in Australia.  Gillard was born in Wales, and is Australia’s second ethnically-Welsh PM.  The first, Billy Hughes, was born in London, but grew up in Wales speaking Welsh as his mother tongue (as did his  contemporary, David Lloyd-George). No other country, apart from Britain and Australia, has had a Welsh prime minister, and Australia has now had two.   Clearly being Welsh is no bar to political success in Australia.  A greater obstacle might be hair-colour:  I believe Ms Gillard is Australia’s first red-headed prime minister.
Australia has had one other PM born in England (Joseph Cook), two born in Scotland (George Reid, Andrew Fisher) and one born in Chile (Chris Watson, although he thought he had been born in New Zealand).  It should be noted that, despite Australia’s historical links with Britain, the Australian High Court has ruled that Britain is a foreign power under the Australian Constitution, which prohibits members of parliament being citizens of foreign powers.
Australia’s very first PM, Edmund Barton, was born in Australia, indeed in the inner-city suburb of Glebe,  Sydney.  A person living in Glebe would now find themselves represented by women at every level of government:

Lord Mayor of the City of Sydney:  Clover Moore
Member of the New South Wales Legislative Assembly for the Electorate of Balmain:  Verity Firth
Deputy Premier of NSW: Carmel Tebbutt
Premier of NSW: Kristina Keneally
Governor of NSW:  Marie Bashir
Member of the Commonwealth House of Representatives for the Federal Division of Sydney: Tanya Plibersek
Prime Minister:  Julia Gillard
Governor-General of Australia:  Quentin Bryce
Queen of Australia and Head of State:  Queen Elizabeth II.

And in this list, the Premier of NSW, Kristina Keneally was born in the USA, while Marie Bashir is of Lebanese descent and Tanya Plibersek of Slovenian. Only in America! as Yogi Berra would say.