If you're running CIC 3.0, there is a column you can add to an Interaction Supervisor workgroup queue view called ACD Wait Reason. This will show you why a call is waiting in queue rather than being delivered to an available agent. It could be that the agent is available, but not activated or not correctly skilled for the call.
For a REALLY detailed analysis, turn up the ACDServer log to 80, replicate the issue and then take a look at the formulas used to select the appropriate interaction and agent. I highly recommend using SnapShot to do this.