A new version of Caller ID was released today, 12/4. It seems to have fixed the Caller ID on PC problem. No new download is needed. The fix was on the server side. So far, it has been working for me (about 5 hours- longest it has worked for months).
Well, turns out it is indeed still broken. It has been reported to my contact in the National Operations Center. They now believe the problem is in the database, and are working with that (major) vendor to resolve the problem.