STAThread missing, but it is there
It might be that you are facing the following problem reported on Connect1:
.vshost.exe forces wrong threading model used when debugging a .exe if a .dll of the same name exists in same bin directory
According to that issue it happens that the hosting process of Visual Studio, i.e. the myprogram.vshost.exe enforces the wrong apartment state when you have both a myprogram.exe and a myprogram.dll file in your output folder.
The problem might be specific to some older version of Visual Studio (2005), and I haven't been able to reproduce it using VS 2010.
The obvious workaround would be to change the name of the dll or to move the dll to another folder.
The situation might have come up because you changed the output type of your project from class libary to Windows application.
1It is unclear whether this problem is confirmed by Microsoft or not, it just says that the problem is outside the responsibility of the VS product team.
You've got an impossible stack trace. It is clear that threading is not the cause of the problem, everything is running on the main thread and the [STAThread] attribute on your Main method is setting the apartment state. The stack trace shows that it indeed the entrypoint.
Well, bad news, some kind of add-on is farking with your main thread. Doing something nasty like calling CoUninitialize too many times. I've had this happen to me once, took me a month to find it. Start diagnosing this with Project + Properties, Debug tab, tick "Enable unmanaged code debugging". That lets you see what DLLs are getting loaded into your program, it is shown in the Output window.
The first lead is when the dialog displays okay the first time but fails the second time. Then you've got some kind of shell extension handler that wormed its way into your program. Use SysInternals' AutoRuns utility and disable any shell extension handler that wasn't made by Microsoft.
It gets harder when the dialog fails right away. Then use Debug + Windows + Modules and go through the list of DLLs. Pay attention to where they came from, shown in the Path column. Distrust anything the doesn't quack like a .NET or Microsoft DLL. Especially not having a Symbol File when you enabled the Microsoft Symbol Server is a lead. A good way to make some headway with this is to compare that list to one you see on another machine that doesn't have this problem.
I do have a war-story about this. My COM code was crashing on hundreds of machines, all I had to go by was a minidump. Took me a month to discover the source, an open source project named ffdshow. Very widely distributed, using different names as well. It had a bug, calling CoUnitialize two times too many. The bug was present in releases for two years but got fixed about a year and a half ago. Very hard to diagnose, I didn't get close to it until I started looking at old releases. If you do see ffdshow in your Modules window then you're close :)
Good luck, let us know the evil-doer.
Can't say without code. If a console app, add the following before you call the method:
Console.Write(System.Threading.Thread.CurrentThread.ApartmentState);
otherwise,
MessageBox.Show(System.Threading.Thread.CurrentThread.ApartmentState);
and see what the threading apartment state REALLY is.