In case someone else has this problem:

I had an Office 2003 application (Access-based) which automated Excel.
When the upgrade to Office 2007 was pushed, I got an error with
"Method "Method 'Open' of object 'Workbooks' failed" when running the
automation within a module, or "The server threw an exception" when
run from the debug window.

After much angst, troubleshooting, and google searching, it turns out
that it was the ApproveIt add-in for Excel... apparently doesn't play
well with being automated in 2007 (although I could open directly or
shell, couldn't automate it).

So, the moral of the story: if you get either of these errors, check
the add-ins. In retrospect it seems obvious, but since it was related
to the push, I was looking at many different things, none of which
were previously functional add-ins.