I had the same problem (and I saw it posted on AWS forums too). The problem is that the console does not update after you unregistered AMI. Thus, they are re-registered for the first time, but they are still listed as if they were. If you try to unregister them again, this will not work and will give a warning (since they have already been unregistered).
. Solution: after clicking "deregistration", click the "update" button in the upper right corner of the console (at the same level as the "Actions" drop down)
source share