OK, I don't know more details, so my propositions are little bit pointless.

The service seems to be working now, so thank you for that.

BTW, wasn't on the old version of relation manager altitude profile of the route?

The restart didn't helped - the queue is still stacked.

I didn't have a chance to try the new services yet, so I have no measure for the waiting times. Waiting times more than few minutes might be big blocker for users of this service (at least for the basic functions).

Separation of queues is good approach, and I can imagine other actions, that can be made to get waiting times shorter or more fair:
-Long running task could be suspended (or pre-detected) and moved to queue with time-expensive tasks for later completion.
-There could be more running tasks at time (could help on multi processor/core system, and also could help to outrun long-running tasks).

I have written you private message about this. I taught, that the service have been temporally frozen, but now I see, that the problem lasts for longer time. I am waiting about an hour now without any change in order, which is very annoying.

If this is because the service is blocked by one task, there obviously should be timeout. I would expect maximum timeout for task about 1 minute (depends on service usage, could be altered dynamically).