It's legit. Really common issue on OS X, iCloud will keep prompting to login even though it already is.
You can try log out of iCloud in System Preferences, then log back in. This should make a positive impact on restart. Also restart your Mac with 'Reopen windows when logging back in' disabled.