One thing to make clear is that it's not the stand alone Google Talk application. It's the chat inside gmail when you're logged in that can handle video calls. The person you're calling should also be logged into his or her gmail account. Vtok for iphone etc can also be visible in the gmail chat, but that won't work. For now it's only pure gmail chat that can do the magic.

If you can't call them, ask them to make a video call you to you first and see what happens.