What is in the "Path Unavailable Answer Point Directory Number" setting on the ACD Paths screen? What happens if you call the number specified there?
Do you have MiContact Center? If so, what is displayed in the Avail and Unavail columns in Queue Now for that queue?