Well to start, the Cisco Switch has nothing to do with it so you can put that out of your mind.
The first thing I'd have you do is verify your licenses. Go to the configuration->> licensing>>system capacity and check to be sure that you have available licenses. I know you said you do, but check.
Next, go to the form "IP Telephones - All". Look for the phones that are out of service. You can get an idea of what extension number are programmed but don't have a phone attached.
Ralph