Ugh, I just updated my iPod and tried messaging my boyfriend over iMessage and the exact same thing happened to me. I was just trying to read through and comment on a discussion in the Apple community threads and it rejected my Apple ID about 30 times before I completely freaked out. I hated Apple before all this nonsense, but now I'm just plain pissed. I updated today thinking, "How can my iPod get any worse?" Well, I just found out how. Before it rejected my ID I saw someone say that on their iPad, they had this issue and they just went into their wifi settings, clicked the blue arrow on their connected network, and then clicked "Renew lease" and then iMessage started working fine. It didn't work for me, but it might work for someone else.
update: went to school, iMessage worked perfectly fine and was faster than it's ever been on the school's network, and faster than it's been, ever, anywhere. i just got home, and it doesn't work again. convinced that my internet is total ? I think yes.