What does the client say it's doing for the first task? Does it get the task at all?
What if you try a different task type, like Script tasks - do they have the same problem?
Are you using Site Servers, or just the NS to connect to from the client for Task?
It's possible you have either communication issues, or performance issue "gumming up the system" so-to-speak.