Switching Carriers with Apple Watch Cellular?

That's simply not true. An Watch is capable of working with any of these three providers and others who use the same technology as they do in the US:

The screenshot above is from this Apple site: Apple Watch - Carriers - Apple.

Have you tried talking to more than one person at Verizon?

When you purchase the Series 3 watch you are not asked who your carrier is as it doesn't matter. It does with an iPhone.

Hi

Apple's instructions for changing carriers are detailed in the first support article below, under the heading "Changing carriers" and, if necessary, also under the heading "Remove your cellular plan":

• Set up and use cellular on Apple Watch Series 3 (GPS + Cellular)
• Apple Watch - Carriers - Apple

If your carrier is experiencing issues with implementing the change, then I suggest that you continue your dialogue with them and, if necessary, also with Apple Support.

Make sure they were referring to the watch and not the iPhone since the watch can't be used with cellular without an iPhone on the same account and AT&T phones are not compatible with the Verizon system unless it is unlocked and has both technologies inside.