Do you have a gmail account? Try Google Voice from within the browser. Or if you have an iOS device, there are a number of applications (like TalkTone) that allow you to make calls using Google Voice. Once you can make calls on the same network from something outside of the GTalk app, you'll have at least narrowed down the problem to the app.
IIRC you should be able to make free North American calls at least until the end of 2012. (This free period has been extended for the past two years). For international calls you could purchase Google credit.
Similar to Skype, I don't think you would be able to purchase a Canadian number due to our Telco/CRTC regulations.
MBP: Santa Rosa 2007 2.2GHz/4GB/256SSD (ML)