Why did you buy a Verizon M8 to use on AT&T? If you're on AT&T, get the AT&T version. There's a reason carrier specific versions are sold, and it's not only because the carriers are evil demons out to butt rape your wallet.
The network designs of Verizon and AT&T are radically different, and even if the M8 has the hardware for both the different variants are designed out of the box to only work with one.
So, even if you did get it to work with AT&T's network, who knows what kind of problems you may be experiencing. It may just be network congestion, it may be something else. Point it, it's tough to troubleshoot when you bought a device from the wrong carrier, as you just introduced a whole new crazy variable into the equation.