Network Blocking Encrypted DNS Traffic

I have a filter software that I place on iPhone in form of a DNS Profile. The DNS profile is necessary for my customers needs so removing it is not an option. Recently, customers have been reporting that when they got a new Verizon Fios router, they are not able to use their iPhone on the wifi, only on data. When connected to the FiOS Wi-Fi they get the following message inn the iphone settings under wifi:

Privacy Warning

This network is blocking encrypted DNS traffic

The names of websites and other servers your device accesses on this network may be monitored and recorded by other devices on this network

Please help! I really need guidance solving this issue.