Try factory reset your device again from recovery menu. It should remove whatever clog is causing services to behave erratically. Also, setup your device as a fresh device add your Google account after device has been setup.
This is what I normally do when I run into setup problems.