The only thing that I have found to work is completely rejailbreaking the device.
The problem is not temporary and despite what the message says, it seems to have nothing to do with a server in any way. It is possible for a device to get this message, and will continue to repeat this message indefinitely every time Cydia is launched. I don't know why. Once I rejailbroke my iPad the problem instantly disappeared.