Okay, so I got a little lazy and never actually rolled back my AppleTV software. (I was simply streaming Netflix to the iPad and then mirroring onto the TV via AppleTV - in the hopes that the problem would be solved for me somehow.) However, my husband became proactive and actually called Netflix for a solution - which I had never attempted.
They claimed that my password had recently been reset to "12345" about a week before. Had I been the one calling, I would have explained that no, in fact, I had not reset my password, and that actually I had "re-reset my password" via their website to what it had always been just a couple days before in hopes of fixing the problem.
I guess the "re-reset" to my original password never "communicated" itself to Apple TV, because when they changed the "12345" password at Netflix HQ, everything was fine. (Odd, because the iPad, iPhone, and website all required my original password, not 12345. And shouldn't AppleTV just check-in with Netflix to confirm this password, rather than require its own unique one. Hmmmm...)
MORE INTERESTINGLY - the other day I downloaded the new Netflix update to my iPad and...lo and behold...same error! This time on my iPad. Luckily, I remembered the issue and tried to log in with the 12345 password, success! So for some reason the password associated with certain devices appears to reset itself to 12345 periodically - perhaps when an update is installed. I dunno. Anyway, seems I got lucky.
Give 12345 a try, may work for you. Best of luck!