Check the name sending you that message. If it's someone on the channel, then it probably means that that channel has it's own nick registry which is separate from nickserv.
If it's coming from nickserv, then you should join the networks help channel (usually #help) and tell them what is happening, since at that point it appears that there's something wrong with the nick service, and the network administrators need to get it fixed.