There have been a few internal queries about this and I think I have finally found the problem. The Excel Services Compat Checker will sometimes say that a workbook is compatible with Excel Services, and when that workbook is loaded on the server, it will fail to load due to "External references (links to other workbooks)".  Sherman Der and I have traced this back to an inconsistency with the Excel OM. It seems like there can be External Workbook References which do not appear in the Excel OM call of Workbook.LinkSources method.

For now, if you are seeing this issue (taking the workbook through the compat checker and then having it not load for the External References reason), please go over the names defined in the workbook (by using the Formulas/Name Manager button) and see if any there translate to a #REF error and seem to contain an External Reference.