Did you have any data connection symbols? (dot, E, 3G, "4G")
I've had problems getting data when on edge, but that's because AT&T's throttling practices are ridiculous, and on edge, they reach beyond even the ridiculous level, into the ludicrous level. They throttle edge pretty hard when you've reached your 3 gig limit on your unlimited plan, which I found out the hard way this weekend. As in, they make edge (which was already slow) unusably slow.
Also, the signal strength is the strength of the connection to your tower. You're only connected to one tower at a time, it's not like you can be connected to a separate tower for data. If data wasn't working at all, but phone calls were, I'd have been hammering the AT&T mark the spot app and/or customer service line. Or at least rebooting the phone once.