Yes, you need a CDMA/LTE Galaxy Nexus for Verizon. The i777 will not work on Verizon.
None of AT&T's LTE phones will work on Verizon, even if unlocked. What AT&T calls 4G that isn't LTE, their HSPA+, is also referred to as WCDMA, plus their 3G is called WCDMA, but its not CDMA like Verizon or Sprint. If that wasn't confusing enough both AT&T and Verizon use 700 MHz LTE, but they are not using the same section of the 700 range so they are not interoperable. Unlike EDGE (2G) that s interopeable on AT&T vs T-Mobile. And some regions of AT&T and T-Mobile se the same 3G frequencies, so some 3G phones have limited functionality on both GSM networks.
Basic rule of thumb, for best results get a phone specifically made for your carrier.