Default 4.4, Play Store only works on wifi

I updated to a 4.4 ROM today, Maximus HD, and I noticed immediately after installing that the Play Store always says "no connection" unless I'm on wifi now. I tried everything I could think of - fixing timezone, date, clearing all the cache I could find, anything.

I eventually tried a second rom, Android Revolution HD. Same thing. Works on wifi, not on mobile data.

Anybody have any suggestions? I'm using an AT&T variant.