That message is really odd, but I strongly suspect it's not accurate. An encrypted backup simply cannot spontaneously become unencrypted, otherwise what good is encryption? It makes no sense. It's far more likely the backup is corrupted, leading to an erroneous interpretation of its encryption status.
I wouldn't rely upon that backup.
wzinet wrote:
As a side note, I'm using an AirPort Extreme for the backup disk.
Assuming you mean a USB hard disk drive connected to an AEBS I'd just get a new one. Not only is one and only one backup less than ideal, the most likely cause for your problems is simple, mundane, hard disk drive failure.
The other one will still retain its backup history should you need it, assuming it's intact, and suspect it isn't. Erase it when you're reasonably certain you no longer require it, but the disk itself is probably no good.