It seems that you cannot change your birth certificate if you are married, in Australia
http://news.ninemsn.com.au/article.aspx?id=122773
Quote
Sex changer remains male on birth forms
Wednesday Aug 16 18:42 AEST
A woman who underwent sex change surgery has failed to prove that she was discriminated against when her attempt to change her gender on her birth certificate was refused.
The woman, who was born a man, had asked the Federal Court in Melbourne to award her compensation of $1,000 for discrimination on the grounds of marital status by the Victorian Registrar of Births Deaths and Marriages.
The woman, referred to as "AB", also sought to have the decision of the Registrar overturned and for her birth certificate to be altered to show she was now a woman.