Sure you can.
When its GSM side is unlocked, the Verizon Storm works on ATT's GSM network. So do many of the other CDMA+GSM dual mode phones they sell, such as the HTC Imagio.
Here's even a
video of how to unlock the Storm for ATT... if you pay these guys for the code.
However, you can also just ask Verizon nicely for your GSM unlock code and usually get it if you're a customer in good standing.
The only thing you cannot do is get 3G on ATT, because their UMTS frequency is different than Europe and Asia. (GSM is a "world standard" only if the phone supports all the different frequencies.)