When I send for example a 35 KB message to a list of about 3100 subscribers on my server that is hosted by FutureQuest, it takes about 15 to 20 minutes to finish (depending also on current web traffic and server use).
What is the size of the list and the message you try to send?
Do you use Sendmail of SMTP?
What is your web host and the package you have with them?