How can I make the progress bar update fast enough?

The reason for this whole mess is the interpolating animation effect introduced by Vista and W7. It has aboslutely nothing to do with thread blocking issues. Calling setProgress() or setting the Value property driectly, triggers an animation effect to occur, which I will explain how to cheat:

I came up with a hack of setting the maximum according to a fixed value. The maximum property does not trigger the effect, thus you get to freely move the progress around with instant response.

Remember that the actual shown progress is given by: ProgressBar.Value / ProgressBar.Maximum. With this in mind, the example below will move the progress from 0 to 100, repensented by i:

ProgressBar works like this:  
progress = value / maximum

therefore:
maximum = value / progress

I added some scaling factors needed, should be self explanatory:

progressBar1.Maximum *= 100;
progressBar1.Value = progressBar1.Maximum / 100;
for (int i = 1; i < 100; i++)
{
    progressBar1.Maximum = (int)((double)progressBar1.Value / (double)(i + 1) * 100);
    Thread.Sleep(20);
}

Vista introduced an animation effect when updating the progress bar - it tries to smoothly scroll from the previous position to the newly-set position, which creates a nasty time lag in the update of the control. The lag is most noticeable when you jump a progress bar in large increments, say from 25% to 50% in one jump.

As another poster pointed out, you can disable the Vista theme for the progress bar and it will then mimic the behavior of XP progress bars.

I have found another workaround: if you set the progress bar backwards, it will immediately paint to this location. So, if you want to jump from 25% to 50%, you would use the (admittedly hackish) logic:

progressbar.Value = 50;
progressbar.Value = 49;
progressbar.Value = 50;

I know, I know - it's a silly hack - but it does work!

It sounds like you're doing everything on the UI thread and thus not releasing the message pump. Have you tried using smoething like BackgroundWorker and the ProgressChanged event? See MSDN for an example.

BackgroundWorker is ideal for loading external data - but note that you shouldn't do any data-binding etc until you get back to the UI thread (or just use Invoke/BeginInvoke to push work to the UI thread).