Free applications from the Android Market have been available since at least day one of the HTC Magic release in New Zealand. Apparently local currency conversion has stopped paid applications up until now.
Today, our dedicated Android forum member, Rob, has just posted a note saying that paid apps quietly appeared last night. I guess the currency issue has been resolved. You can check out some of the top-selling paid applications on the Anroid Market here.