Which client ?? I have found call queues work fine with PC based client software but is super flaky with Mac / mobile clients, exhibiting exactly the behaviour you describe. The issue was officially supposed to have been fixed a little while ago but the solution does not seem robust. Anyway, try the CQ's with only windows clients logged in and see if it works then.
