iOS 8 AppleID/iCloud says pass/id incorrect, but definitely not
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.