On a Google Apps account, you have to add a few DNS records to enable chat federation. if you login to your Apps admin account and visit the Chat settings, you'll see a link to:
Login to your domain management console (GoDaddy or whoever) and add the DNS records as listed in the Google support article.
This hosting company provides a useful test site here for troubleshooting:
I had the same issue and after updating my DNS records, the test passed, and I was able to chat with federated (non-Google) users on talk.google.com.