Comment 3 for bug 833499

I've commited to cloud-init's trunk an improvement to cloud-init that works around this.
The fix there changes updating of .ssh/authorized_keys to update existing entries rather than appending. In this case, then, the inserted key is re-written appropriately.