the autostart issue may be the storage+permission migrations. for me, when upgrading 4.4=>4.5 with ota/ssu, android wont start at boot until i create the android_storage migration-completed marker files. and like you also found, fresh install works fine.
when it doesnt work, i get ‘Unable to start’ status in journalctl on boot, but start works the second time. creating the migration completed files seems to fix it, and removing them seems to cause it, so i assume that one of the migrations is failing.
i think maybe it is somehow related to my permanent media providers CPU drain. who knows