Be aware of what you're actually doing when setting a completion handler for NSInvocationOperation: When such operation finishes, the following happens (From NSOperation Class Reference):
The exact execution context for your completion block is not guaranteed but is typically a secondary thread. Therefore, you should not use this block to do any work that requires a very specific execution context. Instead, you should shunt that work to your application’s main thread or to the specific thread that is capable of doing it. For example, if you have a custom thread for coordinating the completion of the operation, you could use the completion block to ping that thread.
So firstly, the block is executed on a secondary thread (so it'll enter that thread's queue, and when its turn finally comes, it just sends another job to the main thread's queue). That means it'll get mixed in such queue with other pending jobs, like the last updates for the pins that were sent over to the main queue from your timeConsumingOperation:
selector.
And here comes the problem: If you don't set priorities for different jobs, there's no way to tell the order in which such jobs will be finally processed, even if you know they were sent before in time. Furthermore, in your case, the fact that your NSInvocationOperation has finished doesn't necessarily mean that all your objects have been drawn in screen by the time the block is called it only means they have been sent to the UI update thread to be processed when their turn comes.
With this in mind, and given that you don't wanna go the GCD way, (which I'd recommend to give another try as I know it's not easy at the beginning but when you pick up with it you realise it's a wonderful solution for almost all multithreading stuff you'd like to do on an iPhone) I'd create a NSOperationQueue and would send all the jobs there (the one that removes the HUD included, but with lower priority than the others). This way you make sure the removal of the HUD is processed in the main queue after all the 'pin' jobs are done, which was your first goal.