Where are you located? Most NYC customers are reporting success.
Had to reboot my phone twice but it works! 4S - iOS 6.01
Chicagoland area.
I just tried it today on my iPhone 5 AT&T 5gb data plan I live in Lewisburg PA, I did a hard reset and now I am able to facetime over cellular!
Since you're on a tiered data plan, you're capable.
The ones without it seem to be those of us with the grandfathered Unlimited data plans.
I believe I read that AT&T was starting to allow Facetime over cellular if you have an unlimited plan? Don't know if I dreamed it but from what I remember, people were starting to see that they could use FT without having a regular plan. Mine says I need to have an eligible data plan so I can only use it over WiFi. My daughter's phone is on the 3GB plan so she can use her's anywhere.