As far as the skill changes go, if you add/change/remove a skill from an agent id through the PBX, the agent will have to logout and login to have the change take affect.
If you make the change through CMS or CMS Supervisor, it will happen as soon as the agent is off of a call.
Can you post a copy of the agent's id here?
I would also post a copy of an agent id that is working. It would probably be a good comparison.
As a note, if you're looking at CMS reports sometimes you'll notice that there is a call in queue even though there is an available agent. This is usually due to a call ringing at an agent's phone, but the agent hasn't actually answered yet. If you see that a call is waiting in queue, but also see that there are available agents, check the list of agents and you should see at least 1 agent with a state of "Ringing." The call is still considered to be waiting in queue until the agent actually answers the call.