iOS 8 AppleID/iCloud says pass/id incorrect, but definitely not I recently changed my AppleID and iCloud passwords. I can log into the services on my Mac, but my iPhone stubbornly refuses. I've already reset all the device's settings, but I still get this error.

I believe it's a connectivity issue of some sort. There are several apps I am trying to update, but they seem to be stuck. Any advice on resolving connectivity issues like these?
I believe it is safe to presume that the problem was the length of my passwords. When I reduced the length from 16 characters to something less everything started working peachy.