Why wasn’t New South Wales in Australia just named New Wales? Was there something icky about the northern half of Wales?
No. There was already a South Wales, and the one in Australia is the New one.
It appears to have been down to Captain Cook, and he took a bit of time to make up his mind.
Some journal entries:
Reference to the official name “New South Wales”
New Wales again (the very next day after he called it ‘New South’)
“New Wales” doesn’t trip off the tongue very easily with those two W’s in a row, and I have never heard any better explanation than “eh, it just sounds right”
Since the question has been answered, allow me to share this highly relevant sketch from Mitchell & Webb. 
To me, it sounds like civil war in Wales, or perhaps some kind of regional snobbery.
The two w’s aren’t that jarring to the tongue or ear. You could even jam them together, as Aussies tend to do, as with “Australian = Striyne”. “New Wales = NeWahls”.
I believe ctnguy’s cite did cover this point rather well
Looking out my window at New South Wales right now I can confirm it look absolutely nothing like Old North Wales, so its accurate.
The context and construction is fine but in Strine (please note spelling, an “I” or a “Y”, never both) that would be NuWahls and as the Narwhal would already be familiar to Cook then NuSuthWahls is just lexicologically more apt.
Could be worse for naming a region… Sort of like “why are they called Kangaroos?” the name Canada allegedly means “that village over there”.
