People think a "hidden" save file dialog box means the computer is frozen
Solution 1:
They decide the "computer" is "frozen" and call in to have it restarted, which my other staff just does.
Here is your problem. This is not a technical fault, so don't try and implement a technical solution.
Instead, you should implement a process whereby every call or ticket for this type of problem actually gets troubleshooted before any action is taken. People tend to stop making silly mistakes when you make them fix it themselves.
If a user calls in with this problem - just ask them if they have any open dialogue windows, or if they have tried pressing ALT+TAB.
Make a wiki item on your help page with some simple troubleshooting steps that the user can take. That way when they call in with this problem, you can ask if they've checked the "My computer is frozen" troubleshooting guide.
Solution 2:
Your problem is step 5, where your other staff restarts the computer without doing even the most basic troubleshooting.
I assume you're referring to IT staff, who should frankly know better, and not make the problem worse, which is what they do when they just reboot the computer without doing even basic troubleshooting. Rectify this problem first, and the user problem will get better.
Your staff needs to show the users why this is happening, while this is happening if there's any hope of having it stick. Not unlike housebreaking a puppy: If you smack it on the nose when it urinates on your carpet, it will learn not to urinate on your carpet. If you wait until 10 minutes after the fact, it won't know why it's being punished, and will never learn. Users, much like puppies, need this immediacy if there's any hope of having them learn anything, and that's why telling them what the problem was after the computer's been bounced isn't working.
Of course, you'll still have infuriatingly dense users who just don't (or won't) get it, but that's out of your control, and frankly a management problem. My advice on that situation is (assuming you are a manager) to talk the managers of your worst offending users, and point out how much productivity (in their department, as well as yours) is being wasted because their users not checking for a simple save dialogue.
By pointing out how their employees refusal or inability to learn simple tasks is hurting them and their departments, those managers will be much more open to solving the problem with the tools at their disposal. When presented with the problem this way I've seen managers in other departments take it on themselves to "train"/"educate" their users on this type of simple thing, and even discipline or terminate employees who just wouldn't or couldn't get it. (As in: "Sorry that you forget your password every 3 hours and can't log in, but it means you're not a productive employee, and we can't afford to employ you anymore. Get out.")
And on a personal note let me tell you: it's quite satisfying to hear a sales manager scream "It's not IT's fault you're too stupid to click a a button!!!"
Solution 3:
This is sometimes due to a design limitation in x64 Windows with regards to interaction between 32-bit applications and 64-bit drivers. In addition to print dialogs, another common scenario where this occurs is when using 32-bit Internet Explorer and dialogs for smart cards.
Microsoft provides some background information on the cause here:
The Save As dialog box appears behind a 32-bit application when you print to an XPS Document Writer printer on a 64-bit version of Windows 7
http://support.microsoft.com/kb/2567869
Printer drivers are implemented as dynamic-link libraries (DLL) that are loaded into a process that is printing. Printer drivers are implemented as 64-bit DLLs on 64-bit versions of Windows. Printer drivers are implemented as 32-bit DLLs on 32-bit versions of Windows.
A 32-bit process cannot load 64-bit DLLs. Therefore, 64-bit versions of Windows support printing from 32-bit processes through the Splwow64.exe process. Splwow64.exe is a 64-bit process that can load 64-bit printer drivers and handles printing on behalf of 32-bit processes.
When an application calls the StartDoc function to print to the XPS Document Writer printer, the XPS Document Writer printer driver displays a Save As dialog box so that users can specify the name and location of the XPS file. The owner window of the dialog box is typically the active window of the thread that is calling the StartDoc function, and the dialog box will appear over the active window.
When a 32-bit application calls the StartDoc function on a 64-bit version of Windows, the Splwow64.exe process calls in to the XPS Document Writer printer driver on behalf of the 32-bit application. In this scenario, the Save As dialog box is unowned because the thread in the Splwow64.exe process does not have an active window. Additionally, the dialog box may appear behind the application that is printing because the Splwow64.exe process does not have permission to set the foreground window.
The StartDoc call does not return until the dialog box is dismissed, so the application may seem to stop responding.
The Save As dialog box has its own button in the Windows Explorer taskbar if it is created by the Splwow64.exe process. This is because the dialog box is unowned. The taskbar button also flashes when the Splwow64.exe process cannot set the foreground window.