I took a look at the new repro on CI - the only related problem in logs is
2016-04-13 23:51:47.501 19558 INFO nova.metadata.wsgi.server [req-6dcbf363-7715-48f8-8c96-0d287a959a99 - - - - -] 10.109.34.4,10.109.31.3 "GET /2009-04-04/meta-data/public-keys HTTP/1.1" status: 404 len: 195 time: 0.3889701 2016-04-13 23:51:47.676 19557 INFO nova.metadata.wsgi.server [-] 10.109.34.4,10.109.31.3 "GET /2009-04-04/user-data HTTP/1.1" status: 404 len: 195 time: 0.0012429
So far it looks like a rare race condition in Nova, which sometimes leads to 404 errors when cloud-init tries to fetch SSH public keys.
I took a look at the new repro on CI - the only related problem in logs is
2016-04-13 23:51:47.501 19558 INFO nova.metadata. wsgi.server [req-6dcbf363- 7715-48f8- 8c96-0d287a959a 99 - - - - -] 10.109. 34.4,10. 109.31. 3 "GET /2009-04- 04/meta- data/public- keys HTTP/1.1" status: 404 len: 195 time: 0.3889701 wsgi.server [-] 10.109. 34.4,10. 109.31. 3 "GET /2009-04- 04/user- data HTTP/1.1" status: 404 len: 195 time: 0.0012429
2016-04-13 23:51:47.676 19557 INFO nova.metadata.
So far it looks like a rare race condition in Nova, which sometimes leads to 404 errors when cloud-init tries to fetch SSH public keys.