Seeing this on my Verizon S6 also, and I do have Advanced Calling enabled. Saw the message before enabling Advance Calling and still see it afterward. Is Verizon even using VoLTE yet? I thought it hadn't been rolled out.
And like the other reports, this has never happened on any other Android phone I've used -Samsung Moment, S3, S5, or HTC Evo 4G. Always been able to talk and do web stuff freely at the same time even when people insist you can't on Sprint or Verizon. Never been a problem until now. Disappointing if this is how it's gonna be. This is not the only issue I am having with the S6 but still within my 14-day return period thankfully.