I'm also finding that apt is complaining:
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = (unset),
LC_ALL = (unset),
LC_CTYPE = "",
LANG = "english"
are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
But Locales is selected, and I went through the new dialog to select en_AU...
No idea if this is related to my bind problem though...
JPF