Hey Melissa,

Are you trying to return to teaching in Australia, or some other country? It can make a big difference...

Otherwise, I second what Turnoi said...the requirement for a CELTA, especially with your excellent qualifications and experience, may well not be universal. Keep trying other places.
With what you've got, making you get the added certificate is kind of like refusing to let you drive your Benz because you don't own a tricycle...pretty silly!