One of my clients have had this persistent issue bugging them.
Problem.
When trying to export a list from SharePoint Teamsites to Excel (Office 2007 on Vista), this error always pops up. Sometimes it works once and then the error shows up again on subsequent attempts.
After weeks of trying out different scenarios, the solution is pretty simple.
Solution
Turn off the setting for checking server certification revocation list. :)