Charlie I have the same problem EXCEPT I can make the call VIA my bluetooth headset when I turn my wifi off and just run off verizon.  It doesn't happen all the time, but enough to make me frustrated!  I activate my bluetooth and say call--husband...after a VERY long pause I will get the Svoice stating:  "No network connection...please connect and try again.  If I turn OFF my wifi and activate bluetooth it will work just fine.  The Svoice is painfully slow to respond however, not near as quick as SIRI was for me.  I went to Bestbuy where I bought the phone and they were very puzzled...the GEEK took my phone and pretended to perform a bunch of magic, handed me back my phone and said it was all fixed and I shouldn't have that problem anymore...made a test call and it worked.  Got home and had the same stupid message!
It only does this when I try to use my bluetooth to initiate a call. I can manually select the contact the old fashioned way--with a finger and that will work and my call will go through while connected to my bluetooth.  So like I said, it doesn't do it all the time, but enough to really frustrate me!