Lingering Australia question

Whenever I visit Australia, I ask the locals "You have a state called New South Wales, but where is New North Wales?"

I have yet to receive a good answer.