Blocked because of many connection errors

For our reference: https://ci.lscape.net/job/landscape-system-tests/2680/

I have a cloud deploy where a juju bootstrap in the cloud failed right away. Inspection of logs showed this error in a nova-cloud-controller unit repeating over and over:

2016-06-04 04:29:52.793 29942 ERROR oslo_db.sqlalchemy.exc_filters InternalError: (1129, u"Host '10-96-5-52.scapestack' is blocked because of many connection errors; unblock with 'mysqladmin flush-hosts'")

10.96.5.52 is this particular ncc/0 unit.

Bootstrap attempt timestamp:
04:29:51 INFO lib.juju.environment . . 2016-06-04 04:29:51 INFO juju.provider.openstack provider.go:243 opening environment "cloud1-region1"
04:29:52 INFO lib.juju.environment . . 2016-06-04 04:29:52 DEBUG juju.environs.configstore disk.go:351 writing jenv file
04:29:52 INFO lib.juju.environment . . 2016-06-04 04:29:52 DEBUG juju.environs.configstore disk.go:475 writing jenv file to /tmp/jenkins/workspace/landscape-system-tests/build-area/region-juju-home/environments/cloud1-region1.jenv
04:30:52 INFO lib.juju.environment . . 2016-06-04 04:30:52 DEBUG juju.cmd.juju common.go:102 Destroying environment.

Oddly enough, a nova-compute-kvm unit (/1) also shows it:
2016-06-04 04:22:05.883 6179 ERROR oslo_service.periodic_task RemoteError: Remote error: DBError (pymysql.err.InternalError) (1129, u"Host '10-96-5-52.scapestack' is blocked because of many connection errors; unblock with 'mysqladmin flush-hosts'")
But it's address is not 10.96.5.52, it's "dugtrio.scapestack" (can't tell the IP).

I'm attaching all ncc, compute and mysql units' logs, as well as juju status.

I couldn't find mysql logs, the files and directories named like "*mysql*" in the mysql (percona) units were all empty.