then logic would dictate that [progress bars are] pointless
It's not about logic. It's about comfort. During a phone call there is a noise most people don't typically notice. It's called sidetone (comfort noise, in some cases) and the effect of it is to convey a feeling that the connection is 'working.' When that noise is absent the operator perceives that the connection is 'dead.' The phone doesn't sound 'live' somehow.
Logic would dictate that such subtleties are unnecessary. That pesky old Real World thinks otherwise, however, and expends extraordinary effort to perpetuate these irrationalities on nearly all audio systems including land lines, cells networks, radio, voip, etc.
Progress bars the are visual analog to comfort noise. When there is no progress bar, accurate or otherwise, the system appears dead and people become anxious. The progress bar limits that anxiety to mere impatience.
So 'logic' 'dictates' nothing here. It's about keeping people from pulling their hair out.
As to the original question, why is it so hard to make accurate progress bars, the answer is simple; the problem is exactly as hard as creating a time machine. The exact length of any non-trivial operation is unknown until after the operation is complete. When predicting the future becomes easy progress bars will become accurate.
Even the most basic understanding of mechanics and computing should make the answer obvious. I am genuinely astonished that anyone involved with operating a computer would wonder about it.