Sign your new lease but afterwards demand that you want the owner of the apartment to force the OC to give you back your car space. You might also ask for compensation (you've been paying for a car space but didn't get it).
If the owner still does nothing, go to Fair Trading and pay $35 to take action againts tthe owner to refund you the money they took for a car space they didn't provide and to force the owner to take the Owners Corp to the CTTT to give you back your car space.
If it turns out that the car space doesn't belong to the apartment after all (it's possible) the owner of the apartment owes you a refund for the value of a car space in your area.
But I have to stress, if you want to live in this apartment, only take these actions after you have signed a new lease. If the agent is spooked into ending your tenancy you'll find it harder to get your money back, Meanwhile, the agents and Owners Corp are taking advantage of you. A call to Fair Trading (13 32 20) will bring that to an end.