First, after setting up hands-free, did the TomTom offer to set up data services, or did it say you BB was not set up for data (very unlikely)? Next, do you have the appropriate AT&T data plan? I think it may have to be their tethering plan, but I am not sure (search the forum on this).
If so on both of the above, after going through the setup wizard and failing, did it offer to use manual settings (and was your device listed in the setup wizard)?
If you have the correct data plan, you might try again with the wizard before searching the forum for the AT&T settings and trying that way.
TomTom is notorious for having their traffic server off-line, and I have spent a number of frustrating attempts to pair devices only to find the server is down again.