The law is not settled and will shortly be before the High Court (sitting as the Court of Disputed Returns) but theoretically: yes!
The provision on Disqualification is s44, specifically subsection (i):
Any person who:
(i) is under any acknowledgment of allegiance, obedience, or adherence to a foreign power, or is a subject or a citizen or entitled to the rights or privileges of a subject or a citizen of a foreign power,
shall be incapable of being chosen or of sitting as a senator or a member of the House of Representatives.
Which, on the face of it, makes eligibility to sit in the Australian parliament dependent on the citizenship laws of every other country in the world: all 195 of them.
Indeed, right now, any citizen of Australia (which is itself a qualification by virtue of s16 or s34), is allowed to live and work in New Zealand, and to vote after a year's residence - that is they are "entitled to the rights or privileges of a subject [but not a citizen] of a foreign power".
Therefore, interpreted that way, no Australian is entitled to sit in parliament. Of course, a simple referendum1 could change the Constitution to fix that - except, a referendum must be called by parliament and we no longer have one.
Personally, I think it is unlikely2 that the High Court will rule in such a way that would plunge the nation into a constitutional crises by deciding no one can sit in parliament or that who can sit is determined by the laws of foreign nations.
Notwithstanding, at present there are 5 MPs who have been referred to the High Court (2 of whom have already resigned), 2 more who will be referred when parliament resumes in September, 21 known to have been born overseas who have not confirmed that they have renounced any foreign citizenship they might have and an unknown number who may have foreign citizenship by descent.
Each of the cases is distinct: some were born overseas, some have foreign citizenship by descent, one is a 3rd generation Australian whose mother registered him as an Italian citizen when he was a child (17) and he claims he never knew. How the High Court will rule will almost certainly vary with the particular circumstances but its anyone's guess what they will decide. However, it appears that the drafters of the constitution intended that it should capture all dual-citizens, not just those who sought dual-citizenship by a deliberative act.
If a person is found to be ineligible then different things happen depending on if they ware a Senator or a Member of the House of Representatives. For a Senator, the High Court would recount the results of the election - because of the strange way voting works for the Senate, only educated guesses can be made about who would replace whom (especially since the same citizen issue may apply to other candidates on the ticket). For a Member of the House of Representatives, a by-election would be held - because the Liberal/National government has a majority of 1 and 3 of their members are in the gun the results will be ... interesting.
1 Referenda in Australia are not simple. The Australian Constitution is specifically designed to be difficult to change while at the same time granting broad powers to parliament. It takes a nationwide vote and must be carried by a majority of voters nationwide and a majority in a majority of the six states (i.e. 4 or more). Since federation in 1901 there have been 44 referenda of which only 8 have been carried. In is generally accepted that a referendum is impossible to pass unless it has bi-partisan support: and sometimes not even then.
2 And by "unlikely" I mean "impossible" - a conclusion that the constitution must be read in such a way that parliamentary democracy becomes impossible would be contrary to law.
Update in light of the High Court’s ruling: No
Providing a potential parliamentarian has taken “all reasonable steps” to renounce foreign allegiance they are permitted to serve even if the foreign power refuses to allow them to renounce citizenship.
In practice, this means writing to the foreign embassy and renouncing citizenship.