It is the Network. Verizon cannot do voice and data at the same time with any phone. It is a limitation of CDMA as it is currently implemented.
There is a brand new engineering spec (CDMA2009) that has a new way of handling this. In order to implement it it will require changes to the tower gear and phones. Verizon is going to implement LTE instead.
If you want that capability (voice and data at same time) and want an Android phone the only alternative is T-Mobile in the US at this time.