when you post, please post your entire configuration including (but not limited to) your installation method, vicidial version and build, asterisk version, telephony hardware (model number is helpful here), cluster information if you have one, and whether any other software is installed in the box.
Similar to This:
Vicibox X.X from .iso | Vicidial X.X.X Build XXXX | Asterisk X.X.X | Single Server | No Digium/Sangoma Hardware | No Extra Software After Installation
this IS a requirement for posting along with reading the stickies (at the top of each forum) and the manager's manual (available on EFLO.net, both free and paid versions)
Multi Server? Are your agents on the same local subnet as your server? Are the agents SIP phones set to NAT? Have you tried IAX? (KIAX or Zoiper)
I'm shooting in the dark, though, since i'm not at all sure about your installation information (see above)