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:
http://support.google.com/a/bin/answer.py?hl=en&answer=34143
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:
http://www.olark.com/gtalk/check_srv
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.