apt-get nos nós maas é configurado para usar um proxy que está instalado no próprio host maas. Nesse caso, é o host maas que executa a resolução do DNS, e não o nó. Isso parece indicar que seu servidor maas pode resolver nomes sem problemas, mas não seus nós.
Tente isso no nó de bootstrap ("juju ssh 0" para chegar a ele):
dig store.juju.ubuntu.com
Tome nota de seu /etc/resolv.conf
, veja se está correto.
Verifique também /var/log/syslog
no servidor maas e procure por entradas pertencentes ao servidor DNS (bind), pode estar recusando suas consultas por algum motivo.