Recently I ran into a situation where one of our WCF Operations was taking a long time to complete (in the range of a few minutes). The problem was that while this was going on the server stopped responding to all other responses.
After a bit of time with Google I was able to find a post that seemed to explain the problem we were having WCF Threading Internals (Updated).
At the end of the day the solution (which took a bit more work to find) turned out to be fairly simple. It involves making your Operation asynchronous via the AsyncPattern contract parameter (and a bit of other stuff).
So lesson of the day is.. if your WCF Operation is going to take a long time.. Asynch it.