We have switched from COX to Verizon FiOS home triple bundle couple of weeks ago. Phone called Id is not working from the day one and when we call the tech support, they are saying that, the problem with our phone not their service. The same phone was working with COX and Comcast services earlier with no issues.
If its fios digital voice then call in and have them double check. There are three types of fios phone service. Digital voice is a premium voip style service that has extra caller I'd databases involved. Also check how it shows at tnid.org. That may help