Same problem here - Samsung S3, Rogers network, tried 2 different SIM cards. Others in our office are the same.
Rogers rep's first solution was to suggest I reset my phone. Didn't even cross his mind to mention that this would wipe out all my setup - thankfully I asked. He says Rogers has never encountered this error message in 30 years. He said he called Samsung and they aren't seeing any problems elsewhere.
He wanted to swap out my phone for a new one - but that will cost me hours of setting it up again, and now that I found this group, I'm sure it won't even fix the problem.
Appears that Roger could be facing an epidemic.