@eric 

I don't think they are related et all. I am observing this with a fresh new 1.25.5, agents are being uninstalled with the same exact problem:

In this case, I just restarted the machine-19 (among others)

ubuntu@niedbalski-sec-bastion:~$ juju status --format=tabular |grep -i lost
cinder/1                unknown        lost        1.25.5.1 6                                           10.5.1.203     agent is lost, sorry! See 'juju status-history cinder/1'              
  cinder-ceph/1         unknown        lost        1.25.5.1                                             10.5.1.203     agent is lost, sorry! See 'juju status-history cinder-ceph/1'         
mysql/0                 unknown        lost        1.25.5.1 12                                          10.5.1.209     agent is lost, sorry! See 'juju status-history mysql/0'               
openstack-dashboard/0   unknown        lost        1.25.5.1 19      80/tcp,443/tcp                      10.5.1.216     agent is lost, sorry! See 'juju status-history openstack-dashboard/0' 


2016-05-03 15:32:31 ERROR juju.worker.apicaller open.go:169 agent terminating due to error returned during API open: invalid entity name or password

At this point juju was wiped from the system, which I still think is a complete over-reaction.

root@juju-niedbalski-sec-machine-19:/var/log/juju# more machine-19.log 
2016-05-03 15:32:30 INFO juju.cmd supercommand.go:37 running jujud [1.25.5.1-trusty-amd64 gc]
2016-05-03 15:32:30 DEBUG juju.agent agent.go:482 read agent config, format "1.18"
2016-05-03 15:32:30 INFO juju.cmd.jujud machine.go:418 machine agent machine-19 start (1.25.5.1-trusty-amd64 [gc])
2016-05-03 15:32:30 DEBUG juju.wrench wrench.go:112 couldn't read wrench directory: stat /var/lib/juju/wrench: no such file or directory
2016-05-03 15:32:30 INFO juju.cmd.jujud upgrade.go:88 no upgrade steps required or upgrade steps for 1.25.5.1 have already been run.
2016-05-03 15:32:30 INFO juju.network network.go:242 setting prefer-ipv6 to false
2016-05-03 15:32:30 INFO juju.worker runner.go:269 start "api"
2016-05-03 15:32:30 INFO juju.worker runner.go:269 start "statestarter"
2016-05-03 15:32:30 INFO juju.worker runner.go:269 start "termination"
2016-05-03 15:32:30 INFO juju.api apiclient.go:262 dialing "wss://10.5.1.197:17070/environment/34927576-dbfb-459d-8f82-b2c1c0dcd12c/api"
2016-05-03 15:32:30 DEBUG juju.worker runner.go:196 "statestarter" started
2016-05-03 15:32:30 DEBUG juju.worker runner.go:196 "termination" started
2016-05-03 15:32:30 DEBUG juju.worker runner.go:191 stop "state"
2016-05-03 15:32:31 INFO juju.api apiclient.go:194 connection established to "wss://10.5.1.197:17070/environment/34927576-dbfb-459d-8f82-b2c1c0dcd12c/api"
2016-05-03 15:32:31 INFO juju.api apiclient.go:262 dialing "wss://10.5.1.197:17070/environment/34927576-dbfb-459d-8f82-b2c1c0dcd12c/api"
2016-05-03 15:32:31 INFO juju.api apiclient.go:194 connection established to "wss://10.5.1.197:17070/environment/34927576-dbfb-459d-8f82-b2c1c0dcd12c/api"
2016-05-03 15:32:31 ERROR juju.worker.apicaller open.go:169 agent terminating due to error returned during API open: invalid entity name or password
2016-05-03 15:32:31 INFO juju.worker runner.go:275 stopped "api", err: agent should be terminated
2016-05-03 15:32:31 DEBUG juju.worker runner.go:203 "api" done: agent should be terminated
2016-05-03 15:32:31 ERROR juju.worker runner.go:212 fatal "api": agent should be terminated
2016-05-03 15:32:31 DEBUG juju.worker runner.go:248 killing "statestarter"
2016-05-03 15:32:31 DEBUG juju.worker runner.go:248 killing "termination"
2016-05-03 15:32:31 INFO juju.worker runner.go:275 stopped "statestarter", err: <nil>
2016-05-03 15:32:31 INFO juju.worker runner.go:275 stopped "termination", err: <nil>
2016-05-03 15:32:31 DEBUG juju.worker runner.go:203 "statestarter" done: <nil>
2016-05-03 15:32:31 DEBUG juju.worker runner.go:227 no restart, removing "statestarter" from known workers
2016-05-03 15:32:31 DEBUG juju.worker runner.go:203 "termination" done: <nil>
2016-05-03 15:32:31 DEBUG juju.worker runner.go:227 no restart, removing "termination" from known workers
2016-05-03 15:32:31 DEBUG juju.cmd.jujud machine.go:1741 uninstall file "/var/lib/juju/uninstall-agent" does not exist
2016-05-03 15:32:31 INFO juju.cmd supercommand.go:435 command finished