I finally got CallerID working last night after spending a month calling various tech support numbers. I have FiOS digital voice, and though the STB said CallerID was enabled, I never received the notification.
Their solution was to disable callerID from the STB menu, then re-enable. Sounds like there's a known problem where change of service can possibly cause a disconnect between Verizon's system and the status shown on the STB.
The menu says it may take 24-48 hours to register, but in my case, the tech monitored the system as toggled disable/enable and saw the change immediately. I then called from my cell phone, and viola, it's finally working!
