I’d seen these before:

“Your iCloud password for (my account name) is incorrect. Please ensure you are entering the correct password for your iCloud account.”

It usually came up after changing my iCloud password, and having some other computers or iOS devices logged in to iCloud. Just needed to change everything to the same new password, and all was good.

But today that didn’t work, and I couldn’t figure it out… until I remembered that Apple has implemented “per-app” iCloud passwords.

Now if you’ll look at that quote above, you’ll see that it does NOT say “Application “XYXZ” is trying to use iCloud. You’ll need to generate a new one.”

Nope: it simply says that the password for my own iCloud account is incorrect.  But that’s not true. The password for my basic iCloud account IScorrect !  I’m left to figure out not only that it’s an app/iCloud problem, but I have to figure out which app as well.

In my case, it was Fantastical. And not Fantastical per se, but “p18-caldav.icloud.com.”  Yeah. How’s Joe SixPak gonna figure that out?

Here are the instructions for making application-specific passwords:
 
http://support.apple.com/kb/HT6186?viewlocale=en_US&locale=en_US
 
It’s simple enough to do, although you might be mystified that making an “app-specific” password does not ask you which specific app !  It just generates a password, and you use it in whatever app is complaining at the time.
 
I suggest you both check the box saying you want it remembered in your keychain, and also keep a note to yourself of the password itself and where you used it.
I fixed it on one machine by using Keychain Access, and searching on “caldav” and replacing the old password with the new one. On my laptop, I just entered the new password when I got the misleading popup.

Perhaps this was/is completely obvious to everyone except me, but in case there’s someone else out there with the same problem, well… there’s the solution.

hth.