Is it showing edge or EDGE? edge means it has a data connection, but it can't contact the Blackberry servers - which would be an Orange problem.
Can you surf the web? If you can't get EDGE on either T-Mobile or AT&T, you'll need to prod Orange again, as it may be that there is something wrong on their end.