An interview with the agency themselves or with a prospective employer? Have you asked for temporary work or a permanant position?
Last time I used one, I was looking for permanent employment but said that I was prepared to temp whilst looking. I had an interview with the agency 2 days after phoning them and was placed in a temporary role a week after that. Despite being on their books for over 6 months, I didn't get one interview for a permanent role, I found one myself.
I've used one twice now and my experiences have been the same on both occasions.