I've not seen exactly this but we do know that mixed Office installations cause problems with Multiple Uploads as the browser is looking for the presence of a particular office application (of a particular year) based on which Office (year) version it thinks the client is running.
This used to be based on the version of a couple of DLLs - a 2003 one and it looks for the appropriate 2003 Office app and won't accept the correct 2007 Office app.
So the guess is that opening the Office appl. reminds the browser just which version of Office is in use and it then finds the correct app for Multiple Uploads.
I.e. (if the theory is true) solve by removing *any* Office 2003 level apps (or sub-app leftovers) so you are only (100% only) running Office 2007 apps (or remove all 2007 bits if you are running Office 2003)
FAQ sites: (SP 2010)
http://wssv4faq.mindsharp.com; (v3)
http://wssv3faq.mindsharp.com and (WSS 2.0)
http://wssv2faq.mindsharp.com
Complete Book Lists (incl. foreign language) on each site.